Luogu4707 重返现世

题意：有 种物品，第 种物品有权重 ，满足 。

每一轮会随机获得一个物品，获得物品 的概率是 。

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

答案对 取模，，，，时限 。

---

• 前置知识：扩展 Min-Max 容斥。

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

那么 就是这些物品中有其中一个出现所需的期望时间。

每一轮获得 中物品的概率是 ，期望时间就是。

记 为全集， 就是答案。注意到 很大而 很小，改令 为 ，则我们欲求的就是 ，且 。

套用扩展 Min-Max 容斥得：

直接枚举 显然无法承受。注意到 ，考虑和 有关的 DP。

---

左到右逐个加入物品，最终的贡献只和 有关，将它们记录到状态中。

令 表示：前 个物品，选了 个，且 的方案数。

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

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

• 选：
• 不选：

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

复杂度 ，可以拿到 分。

---

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

选择 还是 呢？

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

• 前者是某个东西的倒数，相加将会变得十分难以处理。
• 只有后者与 相关，而 显然是本题的突破口。

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

设 表示考虑了前 个物品， 的 和。

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

• 不选：

• 选：转移开始不对劲了。

  考虑原先的集合 们，全都加入一个元素后贡献变为 我们没有记录 ，组合数很难处理。

尝试把组合数拆开，得到 后面是 。

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

---

设 表示考虑了前 个物品，，且 如所设， 的和。

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

• 不选：
• 选：

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

时间复杂度 ，空间复杂度 。（注意此处的 是原来的 ）

注意有 的情况。