题解 P4707 【重返现世】

Sooke · 2019-01-18 21:19:11 · 题解

前言

的确是一道神仙题……网上都找不到一篇详细的题解，可能是我理解能力太差了吧，硬是瞪了好久才看懂。

为了不让大家思维受阻，这里尽我所能地解释清楚。

解题思路

首先，您需要认识下面这个式子：

它是 扩展 \bold{min-max} 容斥 的根本。其中 max_k(S) 表示集合 S 中的第 k 大元素，min(T) 表示集合 T 中的最小元素，尽管式子看起来及其玄学，但它确实是可以通过构造两个函数然后二项式反演证明的，想了解具体证明过程的读者可以上网自行学习。

有趣的是，上式可以推广到期望，即：

但在这题中，所谓的 E(\max_k(S)) 和 E(\min(T)) 都是什么玩意儿？连集合都没有，而且哪来的相对大小？

我们可以假象每一种原料都有一个出现的时间，因为它们出现的时间互不相同，所以可以构成一个集合，所谓 E(\min(T)) 显然就是 T 包含的原料最早出现的期望时间，E(\max_k(S)) 同理。至于相对大小，因为我们求的本来就是期望，相对对我们来说不重要，只要严格遵循上式计算即可。

为什么要用到这个式子呢？原因是直接算 E(\max_k(S)) 太难了，而 E(\min(T)) ，我们把 T 中、T 外的原料分别看成整体，每次刷到 T 中原料的概率是 \frac{\sum\limits_{t \in T}p_t}{m} ，期望时间自然就是 \frac{m}{\sum\limits_{t \in T}p_t} 。

另外还有一点，题目里给出的 k，实际上代表 E(\min_{k}(S))，以下令 k = n + 1 - k，以简化得到纯正的 E(\max_{k}(S)) 。

好了，该扯的都扯完了，下面我们进入本题最核心的环节——设计 \bold{dp} 。

考虑到 m 和转化后的 k 特别小，很快就能（猜）想出分别给它们一维。完整地，f_{k,\,i,\,j} 表示确定式子中 k 的值，当前是第 i 种原料，\sum\limits_{t\in T} p_t = j 时的 \sum\limits_{T \subseteq S} (-1)^{|T| - k}\ C_{|T|-1}^{k-1} 的值。

状态很复杂对吧，其实本质上就是把 k 和 E(\min(T)) 表示到状态里，给剩下的东西求和，最后再统计状态的贡献。

接下来是转移，很像背包，对于第 i 种原料，如果不选，f_{k,\,i,\,j} = f_{k,\,i-1,\,j}，因为没有影响，如果选呢？就有点复杂了。

对于 i,\,j 这两维，必定分别由 i - 1,\,j - p_i 转移而来，但现在主要问题是，如果直接转移，转移后的所有 |T| 都比转移前大 1（塞了个 p_i 进去），怎么处理其影响？

幸运的是，|T| 大 1，式子里的 (-1)^{|T|-k} 仅仅改了个正负性，而仔细观察 C_{|T|-1}^{k-1}，如果 |T| 大 1，它可以拆成 C_{|T|-1}^{k-1} + C_{|T|-1}^{k-2}（组合数的递推式）！

这就好办多了，拆成两个状态，C_{|T|-1}^{k-1} 的 k 不变，由于 |T| 变了 1，所以 f_{k,\,i-1,\,j-p_i} 对 f_{k,\,i,\,j} 有 -f_{k,\,i-1,\,j-p_i} 的贡献。C_{|T|-1}^{k-2} 的 k 小 1，|T| 也变了 1，负负得正， f_{k-1,\,i-1,\,j-p_i} 对 f_{k-1,\,i,\,j} 有 f_{k-1,\,i-1,\,j-p_i} 的贡献。综上所述，如果选，f_{k,\,i,\,j} = f_{k-1,\,i-1,\,j-p_i} - f_{k,\,i-1,\,j-p_i}。真是神仙！