<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_acabb2500e14aff85d292b49d67a784f, O_RDWR) failed: No space left on device (28) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  session_start(): Failed to read session data: files (path: ) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/auth.php</b> on line <b>430</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
====== Contest Info ======

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

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

===== F. Rainbow Balls =====

**题目大意**：一个袋子里有一些球，有 $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}
$$