牛客练习赛46----C-华华跟奕奕玩游戏

首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/894/C
来源：牛客网
涉及：逆元，递推式

---

题目如下：


关于这个题首先要抓住一个重点，就是每一轮过后，期望就会发现变化，即：

相邻两轮游戏后的期望值是有一个递推关系的

假设第kk轮后黑球数量的期望是a[k]

只要先找到a[k]与a[k+1]的关系，然后通过递推关系找到a[k]的通项公式，并把a[k]的通项公式表示为分数的形式，然后利用分数取模找逆元，就可以得到答案。

---

首先找递推公式：

由于每一轮游戏都会放入一个球，并拿走一个球，所以盒子中球的数量肯定是不变的

由于第k轮后盒子里还剩a[k]个球，那么第k+1轮后，盒子里的黑球数量只有三种可能：
　　1.多放了一个黑球，即有a[k]+1个球；
　　2.仍然是a[k]个球；
　　3.拿走了一个黑球，即有a[k]-1个球；

在来考虑每一种情况的概率：
1.多放了一个黑球，即有a[k]+1个黑球
　则第k+1轮放了一个黑球(注意此时盒子里应该有n+m+1个球,有a[k]+1个黑球)，拿了一个蓝球
　
放黑球的概率是p，拿蓝球的概率是$\frac{n+m+1-a[k]-1}{n+m+1}$n+m+1n+m+1−a[k]−1​，则此情况的概率：
$\frac{p*(n+m+1-a[k]-1)}{n+m+1}$n+m+1p∗(n+m+1−a[k]−1)​
　
2.拿走了一个黑球，即有a[k]-1个黑球
　则第k+1轮放了一个蓝球(注意此时盒子里应该有n+m+1个球,有a[k]个黑球)，拿了一个黑球

放蓝球的概率是(1-p)，拿黑球的概率是$\frac{a[k]}{n+m+1}$n+m+1a[k]​，则此情况的概率：
$\frac{(1-p)*a[k]}{n+m+1}$n+m+1(1−p)∗a[k]​
　
3.仍然是a[k]个球(此情况有两种可能)
　当第k+1轮放了一个蓝球(注意此时盒子里应该有n+m+1个球,有a[k]个黑球)，则拿了一个蓝球
　
放蓝球的概率是(1-p)，拿蓝球的概率是$\frac{n+m+1-a[k]}{n+m+1}$n+m+1n+m+1−a[k]​；
　
　当第k+1轮放了一个黑球(注意此时盒子里应该有n+m+1个球,有a[k]+1个黑球)，则拿了一个黑球
　
放黑球的概率是p，拿黑球的概率是$\frac{a[k]+1}{n+m+1}$n+m+1a[k]+1​

则此情况概率为：
$\frac{(1-p)*(n+m+1-a[k])}{n+m+1}+\frac{p*(a[k]+1)}{n+m+1}$n+m+1(1−p)∗(n+m+1−a[k])​+n+m+1p∗(a[k]+1)​

情况	k+1轮后黑球个数	此情况概率
多放了一个黑球	a[k]+1	$\frac{p*(n+m+1-a[k]-1)}{n+m+1}$n+m+1p∗(n+m+1−a[k]−1)​
拿走了一个黑球	a[k]-1	$\frac{(1-p)*a[k]}{n+m+1}$n+m+1(1−p)∗a[k]​
仍然是a[k]个球	a[k]	$\frac{(1-p)*(n+m+1-a[k])}{n+m+1}+\frac{p*(a[k]+1)}{n+m+1}$n+m+1(1−p)∗(n+m+1−a[k])​+n+m+1p∗(a[k]+1)​

如上表所示，a[k+1]期望为：
$[\frac{a[k]+1}{n+m+1}a[k]+\frac{n+m+1-a[k]-1}{n+m+1}(a[k]+1)]p$[n+m+1a[k]+1​a[k]+n+m+1n+m+1−a[k]−1​(a[k]+1)]p
$+[\frac{n+m+1-a[k]}{n+m+1}a[k]+\frac{a[k]}{n+m+1}(a[k]-1)](1-p)$+[n+m+1n+m+1−a[k]​a[k]+n+m+1a[k]​(a[k]−1)](1−p)
经化简可得：
$a[k+1]=(a[k]+p)\frac{n+m}{n+m+1}$a[k+1]=(a[k]+p)n+m+1n+m​

---

再找通项公式：

为了方便计算，我们设尝数q=$\frac{n+m}{n+m+1}$n+m+1n+m​

即：
$a[k+1]=q(a[k]+p)=q*a[k]+qp$a[k+1]=q(a[k]+p)=q∗a[k]+qp

为了得到通项公式，再设常数x，使得
$a[k+1]+x=q(a[k]+x)=q*a[k]+qx$a[k+1]+x=q(a[k]+x)=q∗a[k]+qx

则qx-x=qp，解得
$x=\frac{qp}{q-1}$x=q−1qp​

又因为a[0]=n，可以得到：

$a[k]+\frac{qp}{q-1}$a[k]+q−1qp​是以$(n+\frac{qp}{q-1})$(n+q−1qp​)为首项，q为公比的等比数列

则
$a[k]+\frac{qp}{q-1}=(n+\frac{qp}{q-1})*q^{k}　(k\ge0)$a[k]+q−1qp​=(n+q−1qp​)∗qk　(k≥0)
即
$a[k]=(n+\frac{qp}{q-1})*q^{k}-\frac{qp}{q-1}　(k\ge0)$a[k]=(n+q−1qp​)∗qk−q−1qp​　(k≥0)
最后，把$p=\frac{a}{b},q=\frac{n+m}{n+m+1}$p=ba​,q=n+m+1n+m​代入,得到
$a[k]=[n-\frac{a}{b}(n+m)]\frac{(n+m)^{k}}{(n+m+1)^{k}}+\frac{a}{b}(n+m)$a[k]=[n−ba​(n+m)](n+m+1)k(n+m)k​+ba​(n+m)
分数统一化，得到
$a[k]=\frac{(bn-an-am)(n+m)^{k}+a(n+m)(n+m+1)^{k}}{b(n+m+1)^{k}}　　(k\ge0)$a[k]=b(n+m+1)k(bn−an−am)(n+m)k+a(n+m)(n+m+1)k​　　(k≥0)

---

分数取模，找逆元：

最后期望
分子fa
$fa=(bn-an-am)(n+m)^{k}+a(n+m)(n+m+1)^{k}$fa=(bn−an−am)(n+m)k+a(n+m)(n+m+1)k
分母fb
$fb=b(n+m+1)^{k}$fb=b(n+m+1)k
我们只考虑余数，所以还需讲fa与fb对mod取余

ll pa=qPow_function(n+m+1,k,mod);
ll pb=qPow_function(n+m,k,mod);
ll fa=((b*n%mod-a*n%mod-a*m%mod)*pb%mod+((a*(n+m)%mod)%mod*pa)%mod)%mod;//多用取余，不然很可能就爆
ll fb=b*pa%mod;

分数取模（$\frac{a}{b}MOD p$ba​MODp），由于mod=1e9+7是一个质数，可以使用费马小定理求解

$\frac{a}{b}MOD p=(a*c)MODp$ba​MODp=(a∗c)MODp
(其中c是b MOD mod的逆元，mod是质数，因此c=b^p-2%p)

ll ni=qPow_function(fb,mod-2,mod);//ni是逆元
return !(cout<<(fa*ni%mod+mod)%mod);//注意fa可能是负数，所以要再加mod并模上mod

---

举例子：
过程只有套fa和fb以及求逆元公式，过于简单，不用举例子，注意要用快速幂求$(n+m)^{k}$(n+m)k和$(n+m+1)^{k}$(n+m+1)k

---

代码如下：

#include <iostream>
#define mod (ll)1000000007
using namespace std;
typedef long long ll;
ll n,m,k,a,b;
long long qPow_function(long long _x,long long _divisor,long long _mod){//快速幂
    long long sum=1;
    while(_divisor){
        if(_divisor&1)    sum=sum*_x%_mod;
        _divisor=_divisor>>1;
        _x=_x*_x%_mod;
    }
    return sum;
}
int main(){
	cin>>n>>m>>k>>a>>b;
	ll pa=qPow_function(n+m+1,k,mod);//pa是（n+m+1）的k次方
	ll pb=qPow_function(n+m,k,mod);//pb是（n+m）的k次方
	ll fa=((b*n%mod-a*n%mod-a*m%mod)*pb%mod+((a*(n+m)%mod)%mod*pa)%mod)%mod;//套fa公式得分子
	ll fb=b*pa%mod;//套公式
	ll ni=qPow_function(fb,mod-2,mod);//求fb模mod的逆元
	return !(cout<<(fa*ni%mod+mod)%mod);
}