Atcoder M-SOLUTIONS Programming Contest C - Best-of-(2n-1)（无穷级数求和+组合恒等式）

无穷级数求和的简单题，稍微写写吧，正好也算帮我回忆下组合数这一块的内容。

首先我们不妨假设 A 赢，B 赢的情况就直接镜像一下即可。我们枚举 B 在 A 赢之前赢了多少局，设为 \(j\)，由于题目规定只要有人赢的局数到达 \(n\) 就停止，因此最后一场比赛必须是 A 赢，而前面相当于在 \(n-1+j\) 个场次中选择 \(n-1\) 场留给 A 赢，剩余留给 B 赢，方案数 \(\dbinom{n-1+j}{n-1}\)，而 A 赢 \(n\) 场的概率为 \(A^n\)，B 赢 \(j\) 场的概率为 \(B^j\)，因此这部分的概率为 \(\dbinom{n-1+j}{n-1}\times A^n\times B^j\)。

接下来考虑平局的问题，按照套路我们枚举有多少次平局，设为 \(i\)，显然 \(i\) 场平局的概率为 \(C^i\)，而将 \(i\) 场平局插入原本 \(n-1+j\) 场分出胜负的比赛，根据隔板法可知方案数为 \(\dbinom{n-1+j+i}{i}\)，最后乘上个比赛次数 \(i+j+n\) 就是期望，因此我们可以初步得到答案的表达式：

\[ans_A=\sum\limits_{j=0}^{n-1}\dbinom{n-1+j}{n-1}\times A^n\times B^j\sum\limits_{i=0}^{\infty}C^i\dbinom{n-1+j+i}{i}\times(n+j+i)
\]

由于这是个无穷级数，无法直接求和，需将其转化为封闭形式后再计算。注意到后面的 \(\sum\limits_{i=0}^{\infty}C^i\dbinom{n-1+j+i}{i}\times(n+j+i)\)，如果不看那个 \(\times(n+j+i)\)，是非常容易转化为封闭形式的，根据生成函数的知识它就是 \(\dfrac{1}{(1-C)^{n+j}}\)，重点在于后面的 \(\times(n+j+i)\) 怎样处理，一个想法是将 \(n+j+i\) 拆成 \(n+j\) 和 \(i\)，前面的 \(\sum\limits_{i=0}^{\infty}C^i\dbinom{n-1+j+i}{i}\times(n+j)\) 相当好处理，直接乘个 \(n+j\) 即可，但是 \(\sum\limits_{i=0}^{\infty}C^i\dbinom{n-1+j+i}{i}\times i\) 比较棘手，我花费了九牛二虎之力找这东西的封闭形式，xtbz，果然 wtcl 了啊（

注意到 \((n+j+i)\) 与前面二项式系数的 \(n-1+j+i\) 只差一个 \(1\)，因此很容易联想到吸收恒等式 \(\dbinom{n}{k}\times k=\dbinom{n-1}{k-1}\times n\)，但是如果直接化后面还是会多出个 \(i\)，等于啥都没干，不过显然 \(\dbinom{n-1+j+i}{i}=\dbinom{n-1+j+i}{n+j-1}\)，而 \(\dbinom{n-1+j+i}{n+j-1}\times(n+j+i)=\dbinom{n+j+i}{n+j}\times(n+j)=\dbinom{n+j+i}{i}\times(n+j)\)，故 \(\sum\limits_{i=0}^{\infty}C^i\dbinom{n-1+j+i}{i}\times(n+j+i)=\sum\limits_{i=0}^{\infty}C^i\dbinom{n+j+i}{i}\times(n+j)\)，噫，好，\(i\) 没了，这下就可以直接套公式求和了，故：

\[ans_A=\sum\limits_{j=0}^{n-1}\dbinom{n-1+j}{n-1}\times A^n\times B^j\times\dfrac{1}{(1-C)^{n+j+1}}\times(n+j)
\]

随便算一下即可，时间复杂度 \(\mathcal O(n)/\mathcal O(n\log n)\)，取决于你怎么实现。

最后，无限 orz ycx，他的方法比我不知道简便到哪里去了！！！11

const int MAXN=2e5;

const int INV100=5.7e8+4;

const int MOD=1e9+7;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,A,B,C,fac[MAXN*2+5],ifac[MAXN*2+5];

void init_fac(int n){

	fac[0]=ifac[0]=ifac[1]=1;

	for(int i=2;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

}

int binom(int x,int y){return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}

int main(){

	scanf("%d%d%d%d",&n,&A,&B,&C);

	A=1ll*A*INV100%MOD;B=1ll*B*INV100%MOD;C=1ll*C*INV100%MOD;

	init_fac(n*2);C=qpow(MOD+1-C,MOD-2);int ans=0;

//	printf("%d %d %d\n",A,B,C);

	for(int i=0;i<n;i++){

		ans=(ans+1ll*binom(n-1+i,n-1)*qpow(A,n)%MOD*qpow(B,i)%MOD*qpow(C,n+i+1)%MOD*(n+i))%MOD;

		ans=(ans+1ll*binom(n-1+i,n-1)*qpow(B,n)%MOD*qpow(A,i)%MOD*qpow(C,n+i+1)%MOD*(n+i))%MOD;

	} printf("%d\n",ans);

	return 0;

}

巴特西

Atcoder M-SOLUTIONS Programming Contest C - Best-of-(2n-1)（无穷级数求和+组合恒等式）

最新文章

热门文章