CF850F

· · 题解

给定 n 种颜色的球，第 i 种颜色的球有 a_i 个，每步进行如下操作：

当所有球的颜色相同时，过程终止。求期望步数。

枚举每种颜色钦定它活到最后，每个情况就是独立的。令 $s=\sum a_i$。 设 $f_i$ 表示钦定的颜色有 $i$ 个球，目标是 $s$ 个球的期望步数，则答案是 $\sum f_{a_i}$。观察 $f$： - $f_0$ 不存在，$f_s=0$。 - 要求的东西的本质是，在位置 $i$ 每步有 $p_i=\frac{i(s-i)}{s(s-1)}$ 的概率 $+1$ 或 $-1$，$1-2p_i$ 的概率不动，$f_i$ 表示从 $i$ 出发，不经过 $0$ 到达 $s$ 的期望步数。 - 对于 $i>1$，有转移 $f_i=(f_{i-1}+f_{i+1})p_i+(1-2p_i)f_i+{\color{red} 1}$，对于 $i=1$，有 $f_1=p_1f_2+(1-2p_1)f_1+{\color{red}1}$。 写出来发现不对，思考一下发现问题可能出在，对于“不能经过 $0$”这个限制，上述转移的处理仅仅是“因为 $f_0$ 不存在，所以把 $f_0$ 视作 $0$”，这样的处理是不合理的。实际上，转移时加上的权值需要再考虑。 另外求出一个 $P_i$ 表示当前在 $i$ 点，最终到达 $s$ 而不经过 $0$ 的**概率**，有 $P_0=0,P_s=1$，转移 $P_i=(P_{i-1}+P_{i+1})p_i+(1-2p_i)P_i$，带状矩阵手动消元/通过一些处理手段可以得到 $P_i=\frac{i}{s}$。 并且，$P_i$ 还可以理解为，从 $i$ 出发的所有路径（以 $0$ 终止或以 $s$ 终止）中，求出每条路径中每步概率的乘积作为权值，则等价于在这些路径中按照权值随机一条走，权值和为 1，其中能到达 $s$ 的路径权值和为 $P_i$。也就是说，把从 $i$ 开始走的这第一步，视作由随机出来的路径决定，则只有 $P_i$ 的概率选择了能到达 $s$ 的路径，这一步对期望步数的有效贡献就是 $1\times P_i$。 注意到此时转移中已经去掉了所有会到达 $0$ 的路径，$f_0$ 不应该再进一步参与实际转移，应该在转移中忽略掉 $f_0$，即视作 $f_0=0$。 接下来，可以对常规转移做一些处理，得到 $f_i-f_{i-1}=f_{i+1}-f_i+\frac{s-1}{s-i}$，则 $g_i=f_{i+1}-f_{i}=g_{i-1}-\frac{s-1}{s-i}$。则 $g_0=f_1-0=f_1$。对于 $i\ge1$，$g_i=f_1-\sum_{j=1}^i\frac{s-1}{s-j}$。 现在仍不可知的是 $f_1$，但已知的是方程 $f_s=0=f_1+\sum_{i=1}^{s-1}g_i$，对于后面那一坨，考虑 $-\frac{s-1}{s-j}$ 在 $i\in[j,s)$ 时均会被算到，共被算到 $s-j$ 次，故总贡献是 $-(s-1)$，同时有 $s-1$ 个这样的 $j$，则 $sf_1=(s-1)^2$，解得 $f_1=\frac{(s-1)^2}{s}$。 此时问题已经解决，因为 $g_0=f_1$ 已知，可以递推依次求得 $g_i,f_{i+1}$ 直到求得 $f_{\max\{a_i\}}$，复杂度瓶颈在于求逆元。每个逆元暴力算可以做到 $O(n+V\log p)$，线性求逆元可以做到 $O(n+V)$，其中 $V=\max\{a_i\}$。