CF850F Rainbow Balls

用期望势能函数做了一下，发现很简单。

题目链接： CF850F Rainbow Balls 。

题目描述：

有 $n$ 种颜色，每种颜色有 $a_i$ 个球。

每秒随机两个球 $i$ 和 $j$ ，将 $j$ 的颜色变成 $i$ 的。

当所有球颜色一样时，游戏结束。

求游戏期望秒数。

经典套路。

令 $m=\sum a_i$ ， $k$ 为当前剩余颜色个数， $\phi(a_1,a_2,\cdots,a_k)$ 表示局面为 $(a_1,a_2,\cdots,a_k)$ 时的势能函数。

设 $\phi(a_1,a_2,\cdots,a_k)=\sum g(a_i)$

那么为了满足条件，有 $\sum E[\Delta g(a_i)]=-1$

然后，对于 $i$ ，有：

$$E[\Delta g(a_i)]=\frac{a_i}{m}\frac{m-a_i}{m-1}(g(a_i-1)-g(a_i))+\frac{m-a_i}{m}\frac{a_i}{m-1}(g(a_i+1)-g(a_i))$$

不妨钦定 $E[\Delta g(a_i)]=-\frac{a_i}{m}$ ，这样就满足了势能函数使用条件。

接着对于 $i$ 分析：

$$\frac{a_i}{m}\frac{m-a_i}{m-1}(g(a_i-1)-g(a_i))+\frac{m-a_i}{m}\frac{a_i}{m-1}(g(a_i+1)-g(a_i))=-\frac{a_i}{m}\\ \frac{m-a_i}{m-1}(g(a_i-1)+g(a_i+1)-2g(a_i))=-1\\ g(a_i-1)+g(a_i+1)-2g(a_i)=\frac{m-1}{a_i-m}$$

令 $d(i)=g(i+1)-g(i)$ ，那么有：

$$d(a_i)-d(a_i-1)=\frac{m-1}{a_i-m}\\ d(x)=d(x-1)+\frac{m-1}{x-m}$$

最后钦定 $d(0)=g(0)=0$ ，就能解出闭式解。