有趣的 DP 优化 min-max 容斥。
题意：给定 $n$ 个物品，每一时刻有 $\dfrac {p(i)}m$ 的概率出现 $i$，问出现 $k$ 中出现 $k$ 中物品的期望。$n\leq 1000$，$m\leq 10 ^ 4$，$|k - n|\leq 10$。
首先考虑答案即为 $n$ 个物品出现时间第 $k$ 小的期望。注意到我们需要利用限制条件 $|k - n|\leq 10$，所以我们将其转化为 $k$ 大问题，则 $k\leq 11$。
考虑扩展 min-max 反演，我们可以得到以下式子：
考虑如何计算所有的 $\min(T)$，那么肯定是 $\dfrac{m}{\sum_{i\in T}p(i)}$，因为是概率的倒数。
但是枚举 $T$ 是 $O(2 ^ n)$ 的，不可接受。注意到答案只与 $|T|, \sum_{i\in T}p(i)$ 有关，而这两个变量分别是 $O(n), O(m)$ 的，考虑按照这个 DP。
记录 $f(i, j)$ 表示选了 $i$ 个元素，他们的和是 $j$ 的方案数和。一次枚举每一个物品，容易得到 $O(n ^ 2m)$ 的转移，但还是无法通过。
注意到 $k$ 很小，但是我们还没有利用到。那么，我们需要去掉一维，然后把 $k$ 压进去，这样做到 $O(nmk)$ 或者 $O(n ^ 2k)$ 的复杂度才可以通过。
但是 $\sum_{i\in T}p(i)$ 这一维是在分母上，压进去很不好转移，我们尝试把 $|T|$ 去掉。记录 $g(i, j)$ 表示如果 $k = i$，和为 $j$ 的答案，不需要最后一项 $\dfrac mj$ 的贡献。
那么我如果要选当前物品的话，那么 $|T|$ 就会 +1，看一下前面的 $(-1) ^ {|T| - k}\binom{|T| - 1}{k - 1}$ 会有什么变化。
通过裂项组合数，我们发现其实裂项开的两项和原式形式是完全相同的，只不过参数发生了变化，一个是 $|T| - 1, k$，另一个是 $|T| - 1, k - 1$。而恰好 $|T| - 1$ 就是我们前面计算所得到的，那么这两项都可以由计算得到的 $g$ 来表示！
我们很轻松的得到 $g(i, j)$ 如果要选当前物品的话，我们其实可以由 $-g(i - 1, j - cur)$ 和 $g(i, j - cur)$ 得到。
那么这么做下去，剩下的思路就是按照这个转移，然后算完后统计一下答案即可。时间复杂度 $O(nmk)$（原题的 $k$ 被替换了），可以通过。注意空间复杂度也为 $O(nmk)$，需要滚动数组。
min-max 反演很多都只是一步，后面的步骤需要根据 min-max 发言的结果进一步 DP 等优化。
1 | int main() |