期望+拆贡献+充斥：CF1349D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187

第一步：找性质

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

第二步：转化（难点）

1. 拆贡献：拆成每个人win的期望步数，然后求 $\sum E(i)$

2. 容斥：肯定不能直接算。于是考虑算直到第 $i$ 个人拿完才结束的的期望步数

3. 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， $E(i)=E'(i)-\sum_{j\ne i}(P(i)C+E(i))$ ， $C$ 表示从无到有的期望步数

4. 结合性质：设 $f_i$ 表示当前有 $i$ 个，win的概率。win指的是这个人win才真正win。则 $E'(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);