本文共 2408 字，大约阅读时间需要 8 分钟。

开始有$n$个黑球,$m$个蓝球

每次$p$概率加入黑球,$1-p$加入蓝球,然后随机拿走一个球

问$k$次操作后的黑球期望

大水题

$f[i]$表示第$i$次操作后还剩$f[i]$个黑球

$f[i]=f[i-1]+p-\frac{f[i-1]+1}{n+m+1}\ast p-\frac{f[i-1]}{n+m+1}\ast (1-p)$

化简一下得到$$f[i]=p+\frac{f[i-1]\ast (n+m+1)-f[i-1]-p}{n+m+1}$$

分离系数得到

$$f[i]=(p-\frac{p}{n+m+1})+f[i-1]\ast \frac{n+m}{n+m+1}$$

初始矩阵$[(p-\frac{p}{n+m+1}),f[0]]$

构造矩阵

$$S=\left[\begin{array}{cc}1& 1\\ 0& \frac{n+m}{n+m+1}\end{array}\right]$$

矩阵快速幂即可

但这样还不够快

令$s=\frac{n+m}{n+m+1}$

$f[i]=s\ast p+s\ast f[i-1]$

$f[1]=s\ast p+s\ast f[0]$

$f[2]=s\ast p+s\ast f[1]=s\ast p+s^2\ast p+s^{2}f[0]$

$f[3]=s\ast p+s^2\ast p+s\ast f[2]=p\ast (s+s^2+s^3)+s^{3}f[0]$

这样可以$O(1)$得到解

#include 
   
    using namespace std;#define int long longconst int mod = 1e9+7;const int maxn = 1e6+10;int n,m,k,a,b,f[maxn];struct rce{
   	int m[3][3];	rce() {
    memset( m,0,sizeof m); }};rce operator * ( rce a,rce b){
   	rce ans;	for(int i=1;i<=2;i++)	for(int j=1;j<=2;j++)	{
   		for(int k=1;k<=2;k++)			ans.m[i][j] = ( ans.m[i][j]+a.m[i][k]*b.m[k][j]%mod )%mod;	}	return ans;}rce init(){
   	rce ans;	for(int i=1;i<=2;i++)	ans.m[i][i] = 1;	return ans;}int quick(int x,int n){
   	int ans = 1;	for( ; n ; n>>=1,x=x*x%mod )		if( n&1 )	ans =ans*x%mod;	return ans;}rce quick( rce a,int n){
   	rce ans=init();	for( ; n ; n>>=1,a=a*a )		if( n&1 )	ans = ans*a;	return ans;}signed main(){
   	cin >> n >> m >> k >> a >> b;	int p = a*quick(b,mod-2)%mod;	int pp = p-p*quick(n+m+1,mod-2)%mod; pp = (pp%mod+mod)%mod;	int mu = (n+m)*quick(n+m+1,mod-2)%mod;	rce chu; chu.m[1][1] = pp, chu.m[1][2] = n;	rce gou; gou.m[1][1] = 1, gou.m[1][2] = 1;	gou.m[2][1] = 0, gou.m[2][2] = mu;	chu = chu*quick(gou,k);	cout << (chu.m[1][2]+mod)%mod;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112845720 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！