-
题意简述：(n) 个人，第 (i) 个人有 (a_i) 个饼干，每步等概率随机在 (m=sum_{i=1}^na_i) 个饼干中选一个，这个饼干的持有者会在剩下的 (n-1) 个人中，把饼干传给等概率随机的一个人，求期望多少步之后，某个人持有所有饼干，(2le nle 10^5)，(mle 3 imes10^5)
-
神题
-
首先发现一点：如果结束的条件是某个已知的人持有所有饼干，那么问题会容易很多
-
设 (E_i) 表示最后所有饼干都在第 (i) 个人手上的所有情况的概率乘步数之和（不是期望）
-
(E'_i) 表示结束条件为所有饼干在都第 (i) 个人手上的情况下的期望步数
-
显然有 (ans=sum_{i=1}^nE_i)
-
考虑如何从 (E') 得到 (E)，考虑从 (E_i) 中扣除掉游戏提前结束的情况
-
[E'_i=E_i-sum_{j e i}(E'_j+P_j imes C) ]
-
其中 (P_i) 为最后 (i) 持有所有饼干的概率
-
看上去还是不太好直接求出每个 (E'_i)，但由于只需求所有 (E'_i) 的和，由 (sum_{i=1}^nP_i=1) 得到：
-
[sum_{i=1}^nE'_i=sum_{i=1}^n(E_i-sum_{j e i}(E'_j+P_j imes C))=sum_{i=1}^nE_i-(n-1)(C+sum_{i=1}^nE'_i) ]
-
[n imes ans=sum_{i=1}^nE_i-(n-1)C ]
-
(C) 表示所有饼干都在某个已知的人手上，全部转到另一个已知的人手上的期望步数
-
考虑如何求 (E_i) 和 (C)，其实是一个东西：(f_i) 表示一个人手里有 (i) 个饼干，使这个人持有所有 (m) 个饼干的期望步数
-
则 (E_i=f_{a_i})，(C=f_m)
-
(f) 的转移即为讨论下一步主角手里的饼干是加一减一或不变：
-
[f_m=0 ]
-
[f_i=frac imf_{i-1}+frac{(n-2)(m-i)}{(n-1)m}f_i+frac{m-i}{(n-1)m}f_{i+1}+1 ]
-
可以链上高消，即把 (f_i) 用 (af_{i+1}+b) 的形式表示之后回代
-
注意消元的姿势，避免除以 (0)
-
(O(mlog mod))