题意
有一袋 \(n\) 个颜色球,第 \(i\) 个颜色的球有 \(a_i\) 个。
当袋子里至少有两个不同颜色的球时,执行以下步骤:
-
一个接一个的按照顺序随机取出两个的球,这些球的颜色可能是一样的。
-
把第二个球涂成第一个球的颜色,然后把两个球放回袋子里。
所有这些动作只需要一秒钟。
输出无法操作时候的期望时间,对 \(10^9+7\) 取模。
\(n\le 2500,1\le a_i \le 10^5\)
题解
分别考虑每种颜色。那么设 \(f_i\) 表示当前颜色的球有 \(i\) 个,到没有其他颜色的球时的期望秒数。
设 \(s=\sum\limits_{i=1}^n a_i\),则 \(f_0=+\infty\),\(f_s=0\),\(\forall i \in (0,s),f_i=(f_{i-1}+f_{i+1})p_i+f_i(1-2p_i)+1\)。其中 \(p_i\) 为 \(\frac{i(s-i)}{s(s-1)}\)。
但因为有无穷,这是无法求的。我们需要避开 \(0\)。因为一旦进入 \(0\) 就出不来,所以所有从 \(i\) 到 \(s\) 的合法路径都是不经过 \(0\) 的。那么我们设 \(g_i\) 表示从 \(i\) 到 \(s\) 不经过 \(0\) 的概率,易得为 \(\frac{i}{s}\)。结合其实际意义,我们可以修改上式:\(f_0=f_s=0\),\(\forall i\in(0,s),f_i=(f_{i-1}+f_{i+1})p_i+f_i(1-2p_i)+\frac{i}{s}\)。注意,此时 \(f_0\) 没有实际意义,赋 \(0\) 仅为了运算方便。
此时若用高斯消元,复杂度为 \(O(n^3V^3)\),无法接受。将其化为更简单的形式:\(f_{i+1}-f_i=f_i-f_{i-1}-\frac{s-1}{s-i}\)。因为 \(f_0=0\),我们只需求出 \(f_1\) 即可。再结合 \(f_s=0\),有 \(f_1+\sum\limits_{i=1}^{s-1}f_{i+1}-f_i=sf_1-\sum\limits_{i=1}^{s-1}\frac{s-1}{s-i}s-i=sf_1-(s-1)^2=0\)。则 \(f_1=\frac{(s-1)^2}{s}\)。递推即可。复杂度 \(O(V\log P)\),瓶颈在求逆元。
此题关键在由 \(g\) 得出 \(f\) 的方程。非常巧妙地结合其实际意义。
标签:le,颜色,limits,题解,CF850F,frac,sum From: https://www.cnblogs.com/FishJokes/p/17067386.html