专栏文章

CF1608F MEX counting - Solution

sstrcmp
CF1608F题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mincdgjp
此快照首次捕获于
2025/12/02 00:06
3 个月前
此快照最后确认于
2025/12/02 00:06
3 个月前
查看原文
从这题出发，我决定用一个比较基础的视角来看贡献延迟计算。
首先贡献是一个比较抽象的东西，你可以理解为我们把要算的东西拆成了很多个部分，每个部分之间它们的关系就是贡献。
贡献延迟计算就是考虑到，我们确定了当前位置的值，可能当下并没有影响，但是往后跟它取值相同的那些点，贡献又跟它不同了。这时候我们几乎不可能简单地算出来我们要求的东西。
我们的问题在于哪呢？因为前面有可能选择了当前取值的点，已经计算了它们的贡献，接下来还想继续算的话，我们可能不得不考虑已经选了那些当前取值的点，复杂度指数。
问题就在于前面这些“当前取值”的点贡献计算太早了，让它们在情况变化的时候赶不上变化。
为时尚早，面包机。
这类问题有一种非常鲜明的特征：对于取值相同的点，它们前后不同的状态总体上有二界性。
--
我认为做到这题的人，应该很多人是被 CSP-S2025 T4 引流过来的：
典型的，比如 CSP2025 employ 这道题，我们确定了选了 ii 个，其中拒绝了 jj 个人，问题就在于，我们并不知道其余没选的 cc 中到底还有多少，是 ii 以后还能产生贡献的，我们似乎一定要记录具体的 cc 的状态，这样一定爆炸。
但是你仔细分析性质，就会发现我们决策 ii 拒绝还是不拒绝，也就是 j→j or j+1j \to j \text{ or } j + 1 这个过程。那些 c<j+1c < j + 1 的点，我们早知道往后它们都会跑路。c>j+1c > j + 1 的点，j→j+1j \to j + 1 它们的影响改变的时刻还未到来。现在决策 ii，可能会导致贡献改变的都是那些 c=j+1c = j + 1 的点，它们从可以录用也可以拒绝，变成了遇上就会跑路。那么之前我们填的 c=j+1c = j + 1 的数，为什么我们这么前面就要填它们呢，为什么不到现在再来填呢？！我们就直接假设前面已经填的 c=j+1c = j + 1 的位置全部都是未知的，不考虑它们贡献的，那么我们面前就是一个旷野啊！
这样我们为了分开 ii 前后 c=j+1c = j + 1 的位置的贡献，只需多记录一个已用了 kk 个 >j> j 的位置。前面 ii 个位置，我们枚举 tt 个 c=j+1c = j + 1 的，贡献是桶的组合数和关于 tt 的排列数，再乘上 ii 位置满足我们决策的选取方案，清晰明了简单极了！
如果你要一个形象的比喻：
  • 线段树的懒标记跟它思想是很类似的。
  • 无需时刻保持敏感，迟钝有时即为美德。尤其与人交往时，即便看透了对方的某种行为或者想法的动机，也需装出一副迟钝的样子。此乃社交之诀窍，亦是对人的怜恤。
再来想想这道题，我们要让前缀 mex\text{mex} 序列的每个元素跟 bb 的距离 ≤k\le k。
最经典的，我们令 fi, jf_{i,\,j} 代表前 ii 个数 mex\text{mex} 是 jj 的方案数。
令前缀的 mex=j\text{mex} = j，那么我们前缀已经考虑到的数的集合，真的是两眼一黑啥情况都不知道，我们随便在 ii 填一个数，都可能会导致 mex\text{mex} 的剧烈变化，这怎么可能做得了呢！
既然大于 jj 的，我们知道在 ii 以前，它们除了当个占位符没任何用处，那之前我们连它们当占位符的贡献都懒得考虑。
那么为了在情况变化的时候算贡献，有什么信息是需要额外记录的呢？当然是像上面那题一一样，记录前 ii 个数有多少种大于 jj 的数被用过（如果你记录位置数也能做，但是你会得到一个极难继续优化的形式）。
fi, j, kf_{i,\,j,\,k} 为前 ii 个数，mex=j\text{mex} = j，kk 种 >j> j 的数已经被用过。我们只考虑 <j< j 的数的排列，和这 kk 个 >j> j 的数颜色可重集关系的方案数。
先来考虑 mex\text{mex} 不变的贡献，mex\text{mex} 不变当且仅当 ai≠ja_i \ne j，这当然是普及组难度：
填入的数小于 jj：在小于 jj 的数中选取一个，fi, j, k←fi−1, j, k×jf_{i,\,j,\,k} \gets f_{i - 1,\,j,\,k} \times j。
填入的数大于 jj：1. 填入的数在 kk 个数中，同上 fi, j, k←fi−1, j, k×kf_{i,\,j,\,k} \gets f_{i - 1,\,j,\,k} \times k。2. 不在，这时候当然不用考虑，fi, j, k←fi−1, j, k−1f_{i,\,j,\,k} \gets f_{i - 1,\,j,\,k - 1}。
现在考虑填入的数是 jj，我们的 mex\text{mex} 是 jj，要变成 tt，那么：
  • 前面 [j+1, t−1][j + 1,\,t - 1] 都要出现过，有顺序的填入到 kk 个空中，要求所有空都被填上（为什么是 kk 个空，因为我们已经考虑完了颜色可重集关系，现在只需要考虑将每个颜色填好）。不难发现这是经典插板法。
我们有：
fi, t, k←∑j<tAk+(t−j−1)t−j−1fi−1, j, k+(t−j−1)f_{i,\,t,\,k} \gets \sum_{j < t} A^{t - j - 1}_{k + (t - j - 1)}f_{i - 1,\,j,\,k + (t - j - 1)}
答案计算也是乘类似的排列数，比较简单。
只保留有效状态复杂度是 Θ(n2k2)\Theta(n^2k^2) 的。
想办法优化一下复杂度，其实可以直接做了但边界上很麻烦，我们变形一下，令 c←k+t−1c \gets k + t - 1。
fi, t, k←∑j<tAk+(t−j−1)t−j−1fi−1, j, k+(t−j−1)fi, t, k←∑j<t(c−j)!j!fi−1, j, c−j\begin{aligned} & f_{i,\,t,\,k} \gets \sum_{j < t} A^{t - j - 1}_{k + (t - j - 1)}f_{i - 1,\,j,\,k + (t - j - 1)}\\ & f_{i,\,t,\,k} \gets \sum_{j < t} \dfrac{(c - j)!}{j!}f_{i - 1,\,j,\,c - j}\\ \end{aligned}
把 1j!\dfrac{1}{j!} 提出去然后维护前缀和即可，复杂度 Θ(n2k)\Theta(n^2k)。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...