一个期望题

· · 个人记录

净是些“意识流”的胡扯……

题目描述

现在有 m 个集合，第 i 个集合中有 a_i 个球。总共有 n 个球。初始状态时，所有球都是白色的。然后，每次操作等概率地将 1 个球涂黑（可能重复涂黑）。当剩余的白球全部属于一个集合时停止。问操作的期望步数。

感（che）想（ dan）

这道期望题，给人的感觉有些抽象。如果用太具体的方法去做，总会陷入一些麻烦之中。

考场上一直在想 Min-Max 容斥：先枚举最后剩余哪个集合，再枚举剩下多少个，然后再算出选的球的最晚出现时间，然后再转化成 Min……但是这是一个很有问题的做法。首先，在Min-Max容斥的过程中，我们没法保证在第一次应该停止的地方停下来，也就是说可能会做很多没必要的操作（其实正是本题的难点所在）；其次，时间复杂度是 O(n^2)。

这道题实际上也不适合用 Min-Max 容斥做，因为 Min-Max 容斥往往用来求一些比较具体的东西，比如，比较明确的第几大……

正解

先考虑枚举最后剩余的哪个集合，设为 i。然后我们要算出把其他的 n-a_i 个点全部涂黑的期望步数。

现在考虑DP，设 f_i 为涂黑 i 个点的期望步数，如果转移方程是这样的（大部分人的第一直觉）：

f_i = f_{i-1}+\frac{n}{n-i+1}

也就是在涂黑了 i-1 个的基础上，再去剩余的 n-i+1 中涂黑一个点。为了方便理解，我们将 \cfrac{n}{n-i+1} 变成更基础的形式：

\cfrac{n}{n-i+1}=\sum_{k=1}^{+\infty}k\left(\frac{i-1}{n}\right)^{k-1}\frac{n-i+1}{n}

权值是 k。概率分成两部分，前面的是在已经选的 i-1 个中的，后面的是新选一个点的。

但是这样的话，相较于之前的 Min-Max容斥丝毫没有进步，因为，我们重复涂黑的是已经选中的，剩下没有涂黑的就 永远不会被涂黑。

但是，如果我们像我们所需要的那样，先钦定了 i 个点的话。我们就会把转移方程转化成这样的：

f_i = \frac{n}{i} + f_{i-1}

还是将新的期望变成更基础的新式：

\frac{n}{i} = \sum_{k=1}^{+\infty}k\left(\frac{n-i}{n}\right)^{k-1}\frac{i}{n}

概率的两部分中，前一个就是在除了 i 个球中选的次数。这样我们就会在涂黑 n-a_i 个球的同时，任意地涂黑一些 i 剩余的集合中的某些球。

但是这样的DP还是不完备的，因为这会遇到一个问题：如果我们钦定的集合 i 不是最后剩余的。那么我们就要减掉其对应的期望。也就是，全部的球都涂黑且 i 不是最后一个的涂黑的：

f_n\times\frac{m-1}{m}

代码

    for (int i = 1; i <= n; ++i)
        f[i] = (f[i-1] + n * inv(i,mod-2)) % mod;
    for (int i = 1; i <= m; ++i) 
        Plus(ans, f[n-a[i]] - f[n] * (m-1) * inv(m));