practice link

题目大意：一个袋子里有一些球，有 $n$ 种颜色，第 $i$ 种有 $a_{i}$ 个。每回合从中依次摸出两个球，然后将第二个球的颜色变为第一个球的颜色，然后再放回。直到所有球的颜色相同为止。求回合数的期望。

题解：对每种颜色分别计算，那么除了当前的颜色，其他颜色是什么都没关系。

设球的总数是 $S$，$E_{x}$ 表示当前有 $x$ 个球时的“期望”。这里的期望事实上要排除掉最终使得球数为 $0$ 的情况，这种情况不应该在这里计算。推一下这种“期望”的线性性可以知道，一回合的代价不应该是 $1$，而应该是使得球数为 $S$ 的概率，设为 $p_{x}$。

那么有

$$ \begin{aligned} p_{0}&=0\\ p_{S}&=1\\ p_{x}&=\frac{1}{2}(p_{x+1}+p_{x-1}) \end{aligned} $$

由此可知 $p_{x}=xp_{1}$，从而 $p_{1}=\frac{1}{S}$。

那么对于一般的 $x$ 有

$$ \begin{aligned} E_{x}&=\frac{x(S-x)}{S(S-1)}(E_{x+1}+E_{x-1})+(1-2\frac{x(S-x)}{S(S-1)})E_{x}+\frac{x}{S}\\ 2E_{x}&=E_{x+1}+E_{x-1}+\frac{(S-1)}{(S-x)}\\ E_{x+1}-E_{x}&=E_{x}-E_{x-1}-\frac{S-1}{S-x} \end{aligned} $$

如果我们从 $E_{0}=0$ 开始递推，可以得到

$$ E_{x}-E_{x-1}=E_{1}-\sum_{i=1}^{x-1}\frac{S-1}{S-i} $$

$$ E_{x}=xE_{1}-\sum_{i=1}^{x-1}\frac{(S-1)(x-i)}{S-i} $$

而且 $E_{S}=0$，因此

$$ \begin{aligned} 0&=SE_{1}-\sum_{i=1}^{S-1}(S-1)\\ E_{1}&=\frac{(S-1)^{2}}{S} \end{aligned} $$

从而

$$ E_{x}=\frac{(S-1)^{2}x}{S}-\sum_{i=1}^{x-1}\frac{(S-1)(x-i)}{S-i} $$