====== Contest Info ======

[[http://codeforces.com/contest/1349|practice link]]

====== Solutions ======

===== D. Slime and Biscuits =====

**题目大意**：有 $n$ 个口袋，每个口袋有 $a_{i}$ 个球。每次等概率随机一个球，将其等概率随机移动到另外 $n-1$ 个口袋中的一个。当所有球在同一个口袋时结束。问期望移动次数。

**题解**：设 $E_{i}=\sum_{j=0}^{+\infty}jP_{ij}$，其中 $P_{ij}$ 表示在 $j$ 步后所有球在 $i$ 中的概率。注意 $E_{i}$ 本质上不是一个期望，因为其概率之和不为 $1$。答案为 $\sum_{i=1}^{n}E_{i}$。

设 $E'_{i}$ 表示仅当所有球在 $i$ 中时游戏才结束的期望，$P_{i}=\sum_{j=0}^{+\infty}P_{ij}$。其中 $\sum_{i=1}^{n}P_{i}=1$。

那么有 $E_{i}=E'_{i}-\sum_{j=1,j\neq i}^{n}(P_{j}E+E_{i})$，其中 $E$ 表示从所有球在口袋 $i$ 开始，直到所有球在口袋 $j(i\neq j)$ 结束的期望，显然这对任意 $i,j$ 都相同。

将 $n$ 个式子相加可得，$n\cdot\text{ans}=\sum_{i=1}^{n}E'_{i}-(n-1)E$。

至于 $E$ 和 $E'_{i}$ 的计算，则是经典的一维随机游走，这里就不赘述了。

时间复杂度 $\mathcal{O}(\left(\sum_{i=1}^{n}a_{i}\right)\log\sum_{i=1}^{n}a_{i})$。