期望+拆贡献+充斥：CF1349D

第一步：找性质

每个人的期望步数只与总数量 $m$，总人数 $n$，自己数量 $a_i$ 有关

第二步：转化（难点）

1. 拆贡献：拆成每个人win的期望步数，然后求 $\sum E(i)$
2. 容斥：肯定不能直接算。于是考虑算直到第 $i$ 个人拿完才结束的的期望步数
3. 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献，$E(i)=E^{\prime }(i)-{\sum }_{j\ne i}(P(i)C+E(i))$，$C$ 表示从无到有的期望步数
4. 结合性质：设 $f_i$ 表示当前有 $i$ 个，win的概率。win指的是这个人win才真正win。则 $E^{\prime }(i)=f_{a_i},C=f_0$
5. 消掉 $E(i)$：考虑涉及全部，则直接求 ${\sum }_{E(i)}$，然后就可以约去了

第三步：推式子

然后发现就是求 $f$，$f$ 直接式子可以简单列出来。然后化简参见上一篇博客

最后考虑 $g_0$ 怎么算。$g_0$ 本质是获得饼干的期望步数，因为概率 $\frac{1}{n-1}$，所以期望是 $n-1$

	n=read(); init(N-1); 
	for(i=1; i<=n; ++i) a[i]=read(), m+=a[i]; 
	g[0]=n-1; 
	for(i=1; i<N; ++i) Add(g[i], g[i-1]*i%mo*(n-1)%mo*inv[m-i]%mo+m*(n-1)%mo*inv[m-i]%mo); 
	f[m]=0; 
	for(i=m-1; i>=0; --i) Add(f[i], g[i]+f[i+1]); 
	Add(ans, -(n-1)*f[0]); 
	for(i=1; i<=n; ++i) Add(ans, f[a[i]]); 
	Mul(ans, inv[n]); 
	printf("%lld", ans); 
1
2
3
4
5
6
7
8
9
10