牛客等级之题 N1(8.3) 题解

题目传送门

题目大意： 一开始箱子里有 $n$ 个黑球 $m$ 个白球，每次有 $p$ 的概率放进去一个黑球，有 $1-p$ 的概率放进去一个白球，放完球后再随机拿一个球，问进行 $k$ 次后箱子里黑球期望个数。

题解

可以注意到每次操作后球数是保持在 $n+m$ 不会变的。

令 $a_i$ 表示进行 $i$ 次操作后黑球的期望个数，显然有 $a_0=n$ 。

有四种情况需要考虑，其中两种是放一个黑球拿一个黑球和放一个白球拿一个白球，这两种不会引起黑球数变化所以不需要考虑。

放一个黑球拿一个白球的概率为： $A=p\times \dfrac {n+m+1-(a_i+1)} {n+m+1}$ ，贡献为 $1$ ，因为多了一个黑球。

放一个白球拿一个黑球的概率为： $B=(1-p)\times \dfrac {a_i} {n+m+1}$ ，贡献为 $-1$ ，因为少了一个黑球。

整理得到： $a_{i+1}=a_i+A\times 1+B\times (-1)=(p+a_i)\dfrac {n+m} {n+m+1}$ 。

令 $T=\dfrac {n+m} {n+m+1}$ ，那么有 $a_{i+1}=Ta_i+pT$ ，展开得到 $a_i=T^ia_0+pT(1+T+T^2+...+T^{i-1})$ ，于是就可以 $O(\log k)$ 计算答案了。

代码如下：

#include <cstdio>
#define mod 1000000007

int n,m,k,a,b;
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;x=1ll*x*x%mod,y>>=1);return re;}
#define inv(x) ksm(x,mod-2)

int main()
{
    scanf("%d %d %d %d %d",&n,&m,&k,&a,&b);
    int p=1ll*a*inv(b)%mod,T=1ll*(n+m)*inv(n+m+1)%mod;
    printf("%d",(1ll*ksm(T,k)*n%mod+1ll*p*T%mod*(ksm(T,k)-1+mod)%mod*inv(T-1)%mod)%mod);
}