CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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}
$$
CVBB ACM Team

用户工具

站点工具

页面工具
