题解 P4707 【重返现世】

· · 题解

题意：有 n 种物品，第 i 种物品有权重 p_i，满足 \sum_ip_i=m。

每一轮会随机获得一个物品，获得物品 i 的概率是 \frac{p_i}{m}。

求收集到 k 种不同物品所需的期望轮数。

答案对 998244353 取模，n\leq 1000，m\leq 10^4，n-k\leq 10，时限 \texttt{2s}。

upd 2025.2.27：重新排版，改正一处错误。

我们设集合 S 为物品集合，物品的权值为第一次出现时间。

那么 \mathbb E[\min(S)] 就是这些物品中有其中一个出现所需的期望时间。

每一轮获得 S 中物品的概率是 \sum\limits_{i\in S}\frac{p_i}{m}，期望时间就是\dfrac{m}{\sum\limits_{i\in S}p_i}。

记 U 为全集，\mathbb E[{\rm kth\,min}(U)] 就是答案。注意到 k 很大而 n-k 很小，改令 k 为 n-k+1，则我们欲求的就是 \mathbb E[{\rm kth\,max}(U)]，且 k\leq 11。

套用扩展 Min-Max 容斥得：

{\rm Ans}=\sum\limits_{T\in S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\mathbb E(\min(T))

直接枚举 T 显然无法承受。注意到 m\leq 10^4，考虑和 m 有关的 DP。

左到右逐个加入物品，最终的贡献只和 |T|,\sum_{i\in T}p_i 有关，将它们记录到状态中。

令 f[i][j][s] 表示：前 i 个物品，选了 j 个，且 \sum_{i\in T}p_i=s 的方案数。

最后把方案数乘以对应贡献求和，就得到答案。

转移：讨论选或不选当前物品

为了节省空间，可以把第一维 i 滚掉。

复杂度 O(n^2m)，可以拿到 70 分。

为了减少状态量，尝试把贡献塞到 DP 值中。

选择 \mathbb E(\min(T)) 还是 (-1)^{|T|-k}\binom{|T|-1}{k-1} 呢？

应当选择后者，理由如下：

把后者加入 DP 值，看看会发生什么……

设 f[i][s] 表示考虑了前 i 个物品，\sum\limits_{i\in T}p_i=s 的 (-1)^{|T|-k}\binom{|T|-1}{k-1} 和。

转移：考虑选或不选当前物品

尝试把组合数拆开，得到

\begin{aligned} \sum_{T}(-1)^{|T|+1-k}\dbinom{|T|}{k-1} &=\sum_{T}(-1)^{|T|+1-k}\left[\dbinom{|T|-1}{k-2}+\dbinom{|T|-1}{k-1}\right]\\ &=\sum(-1)^{|T|-(k-1)}\dbinom{|T|-1}{k-2}-\sum(-1)^{|T|-k}\dbinom{|T|-1}{k-1} \end{aligned}

后面是 f[i-1][s]。

前面和 f 很像，唯一的区别是 k。因此，我们可以对各个 k 同时进行 DP，这样就能转移了。

设 f[i][s][k] 表示考虑了前 i 个物品，\sum_{i\in T}p_i=s，且 k 如所设，(-1)^{|T|-k}\binom{|T|-1}{k-1} 的和。

转移：考虑选或不选当前物品

为了省空间，仍要把第一维滚掉。

时间复杂度 O(nmk)，空间复杂度 O(mk)。（注意此处的 k 是原来的 n-k+1）

注意有 p_i=0 的情况。