Contest Info

date: 2017.09.04 22:35-25:05

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} \]