CF1608F MEX counting - Solution

strcmp · 2025-11-07 20:37:06 · 题解

从这题出发，我决定用一个比较基础的视角来看贡献延迟计算。

首先贡献是一个比较抽象的东西，你可以理解为我们把要算的东西拆成了很多个部分，每个部分之间它们的关系就是贡献。

贡献延迟计算就是考虑到，我们确定了当前位置的值，可能当下并没有影响，但是往后跟它取值相同的那些点，贡献又跟它不同了。这时候我们几乎不可能简单地算出来我们要求的东西。

我们的问题在于哪呢？因为前面有可能选择了当前取值的点，已经计算了它们的贡献，接下来还想继续算的话，我们可能不得不考虑已经选了那些当前取值的点，复杂度指数。

问题就在于前面这些“当前取值”的点贡献计算太早了，让它们在情况变化的时候赶不上变化。

为时尚早，面包机。

这类问题有一种非常鲜明的特征：对于取值相同的点，它们前后不同的状态总体上有二界性。

--

我认为做到这题的人，应该很多人是被 CSP-S2025 T4 引流过来的：

典型的，比如 CSP2025 employ 这道题，我们确定了选了 i 个，其中拒绝了 j 个人，问题就在于，我们并不知道其余没选的 c 中到底还有多少，是 i 以后还能产生贡献的，我们似乎一定要记录具体的 c 的状态，这样一定爆炸。

但是你仔细分析性质，就会发现我们决策 i 拒绝还是不拒绝，也就是 j \to j \text{ or } j + 1 这个过程。那些 c < j + 1 的点，我们早知道往后它们都会跑路。c > j + 1 的点，j \to j + 1 它们的影响改变的时刻还未到来。现在决策 i，可能会导致贡献改变的都是那些 c = j + 1 的点，它们从可以录用也可以拒绝，变成了遇上就会跑路。那么之前我们填的 c = j + 1 的数，为什么我们这么前面就要填它们呢，为什么不到现在再来填呢？！我们就直接假设前面已经填的 c = j + 1 的位置全部都是未知的，不考虑它们贡献的，那么我们面前就是一个旷野啊！

这样我们为了分开 i 前后 c = j + 1 的位置的贡献，只需多记录一个已用了 k 个 > j 的位置。前面 i 个位置，我们枚举 t 个 c = j + 1 的，贡献是桶的组合数和关于 t 的排列数，再乘上 i 位置满足我们决策的选取方案，清晰明了简单极了！

如果你要一个形象的比喻：

• 线段树的懒标记跟它思想是很类似的。

• 无需时刻保持敏感，迟钝有时即为美德。尤其与人交往时，即便看透了对方的某种行为或者想法的动机，也需装出一副迟钝的样子。此乃社交之诀窍，亦是对人的怜恤。

再来想想这道题，我们要让前缀 \text{mex} 序列的每个元素跟 b 的距离 \le k。

最经典的，我们令 f_{i,\,j} 代表前 i 个数 \text{mex} 是 j 的方案数。

令前缀的 \text{mex} = j，那么我们前缀已经考虑到的数的集合，真的是两眼一黑啥情况都不知道，我们随便在 i 填一个数，都可能会导致 \text{mex} 的剧烈变化，这怎么可能做得了呢！

既然大于 j 的，我们知道在 i 以前，它们除了当个占位符没任何用处，那之前我们连它们当占位符的贡献都懒得考虑。

那么为了在情况变化的时候算贡献，有什么信息是需要额外记录的呢？当然是像上面那题一一样，记录前 i 个数有多少种大于 j 的数被用过（如果你记录位置数也能做，但是你会得到一个极难继续优化的形式）。