杭州集训D4T1

题目简述

给定一个大小为\(n\left(n \le 10^5\right)\)的环，每个点初始为白色，每一步在所有点中均匀随机选择一个，将其染黑（已经黑则不变）；然后对于所有白点，如果其左右都是黑色，那么把它变成黑色。当所有点都是黑色时停止。问操作次数的数学期望。

题解

对于题目的一个观察：可以把所有的“自动染黑”操作延迟到最后一步，也就是说，直接无视每一次选择的第二部分，而将终止条件改为“所有的黑点间隔至多为1时终止”。这一步转化非常重要。

首先，选择一个白点一定会导致状态不可逆地转移，而选择一个黑点不会有任何改变。考虑当前有\(x\)个黑点时，不停选择直到选择了第一个白点从而转移走的步数期望，记为\(f(x)\)。在这个状态进行一次选择，要么转移走概率为\(1-\frac{x}{n}\)，要么继续停留在这里概率为\(\frac{x}{n}\)，于是得到一个期望方程\(f(x) = (1-\frac{x}{n}) + \frac{x}{n}f(x)\)，解这个方程易得\(f(x) = \frac{n}{n-x}\)。

接下来，如果去具体考虑一个状态通过什么路径转移到最终状态，就不可避免地要去考察这个环上黑色点的分布情况，复杂度就没法接受。怎么办呢？注意到每一种具体方案都是由一系列上述阶段构成的，而在每一个特定状态停留的时间\(f(x)\)容易计算。所以考虑拆解贡献，把每一个路径的转移次数均摊到每一个上述的阶段中。记\(g(x)\)表示当前已经染了\(x\)个黑点，并且还没有到达终止的概率。如果没有到达终止，这个阶段就会产生\(f(x)\)的贡献，所以最终需要计算的就是\(1+\sum\limits_{k=1}^{n-1}f(x)g(x)\)。

\(g(x)\)的计算，由于每一次选择黑点对于黑点的分布没有贡献，而如果选到白点就相当于在白点中均匀选择，所以可以推知所有选择了\(x\)个黑点的分布方案是等概率的，所以考虑固定第一个位置是黑色（因为环上标号显然不影响），直接计数可以得到\(g(x) = 1 - \binom{x}{n-x}/\binom{n-1}{i-1}\)，于是做完了。