延迟钦定贡献 DP

· · 个人记录

AT_mujin_pc_2018_f チーム分け

现有 n 个元素,你需要将每个元素分到某组中,要求 i 所在组的大小不超过 a_i。求合法分组方案数,对 998244353 取模。

::::::success[题解]

单组限制只关心 a_i 最小的元素。对 a_i 降序排序,考虑按下标逐个加入并计算贡献。

在加入 i 时,如果不记录当前的分组情况,贡献系数难以计算。为此,我们将不决策也作为一种转移,考虑下面的 DP 状态:

复杂度 O(n^3),可以通过原题。

:::::info[延迟钦定 DP]

本题通过延迟钦定的组合意义,解决了贡献系数无法计算的问题。我们将本题的模型进行抽象:

:::::

::::::

P7154 [USACO20DEC] Sleeping Cows P

现有 n 个左部点 a_i 和 n 个右部点 b_i。若 a_i \le b_j 则连边 i \to j。

称二分图的一个匹配是极大的,当且仅当任意失配的左部点无法与失配的右部点匹配。对极大匹配计数,取模 10^9+7。

:::::success[题解]

刻画极大匹配的性质:

我们将 a_i,b_j 扔到一个数组 x 里升序排序,数值相同则左部点在前。此时,失配的右部点全部位于失配的左部点的左侧。

为叙述简便,下文称最终失配的点被放弃,最终得到匹配,但当前失配的点被保留。

考虑延迟钦定 DP:

复杂度 O(n^2)。本题给出了二分图匹配计数的延迟钦定 DP 套路。代码。

:::::

P8321 『JROI-4』沈阳大街 2

给定两个长为 n 的序列 a_i,b_i,保证 a_i 单调不降,a_n \ge \min \limits_{i=1}^n b_i。对 1 \sim n 的排列 p_i,定义权值为

\prod_{i=1}^n \min(a_i,b_{p_i})

每种排列等概率出现,求权值的期望对 998244353 取模的结果。

:::::success[题解]

考虑建 n 阶完全二分图,边 (i,j) 的边权为 \min(a_i,b_j),一组匹配的权值为匹配边边权的乘积,问题即对所有完美匹配的权值求和。

将 a_i,b_i 扔到同一个数组 x 里降序排序。对于 x_i \to x_j 的匹配,边权确定为 x_j。

考虑延迟钦定配对 DP:

复杂度 O(n^2)。

:::::

ARC207A Affinity for Artifacts

现有 n 个任务,第 i 个任务的成本为 a_i。

你初始持有变量 x,以任意顺序执行所有任务。执行第 i 个任务时,x \gets x-a_i,并对 a_j \ge 1 令 a_j \gets a_j-1。

求最终 x \ge 0 的执行顺序数,对 998244353 取模。

:::::success[题解]

设第 i 个任务是第 p_i 个被执行的,约束即为

\sum_{i=1}^n \max(0,a_i-p_i+1) \le x

直接对着 DP 需要记录 \sum a_i 级别的信息。我们转换视角,考虑任务节省的成本。设 k=\left(\sum \limits_{i=1}^n a_i\right) -x,只要

\sum_{i=1}^n \min(a_i,p_i-1) \ge k

若 k>\binom{n}{2} 无解,k \le 0 答案为 n!,这样值域就降到 O(n^2) 级别。

将 i \to p_i 描述为二分图匹配,边权为 \min(a_i,p_i-1),转化为对权值 \ge k 的完美匹配计数。

将 a_i 和 p_i-1 丢到同一个数组 b 中降序排序,则边权由位置靠右的点决定。设计延迟钦定配对 DP:

不难发现,由于 b_1 \sim b_i 的类型确定,状态中 x,y 只需记录一维,另一维可以预处理后算出来。复杂度 O(n^4)。

:::::

ZR3382 冒泡排序 / bubble

对长为 n 的排列 a_i,定义一轮双向冒泡排序为:

  • 顺次枚举 i=1,2,\cdots,n-1,若 a_i>a_{i+1} 则交换 (i,i+1)。
  • 顺次枚举 i=n-1,n-2,\cdots,1,若 a_i>a_{i+1} 则交换 (i,i+1)。

给定 n,k,求 k 轮双向冒泡后变为递增的排列 a 数目。

:::::success[题解]

结论 设 f(a)=\max \limits_{i=1}^n \sum\limits_{j<i} [a_j>i],则排列 a 合法的充要条件为 f(a) \le k。

证明 根据排序网络的 01 原理,任取阈值 x,将 \le x 的数视作 0,>x 的数视作 1,则 a 合法等价于 01 序列在 k 轮双向冒泡后有序。

设 q_x 为前 x 位中 1 的数目,则后 n-x 位中恰有 q_x 个 0。分讨可得,一轮双向冒泡令 q_x \gets \max(0,q_x-1)。

只要 \forall x, q_x \le k。定义 f(a)=\max \limits_{i=1}^n q_i 则 f(a) \le k,证毕。

下面对 f(a) \le k 的排列计数。将 i \to a_i 描述为二分图匹配,从小到大扫描,设计延迟钦定配对 DP:

复杂度 O(n^2),对 j 维度滚动数组即可空间线性。代码。

:::::

CF626F Group Projects

给定长为 n 的序列 a_i。你需要将 n 个有标号元素划分为若干无标号组。组内权值定义为 \max-\min,要求总权值 \le k。求方案数,取模 10^9+7。

:::::success[题解]

将 a_i 升序排序后逐个加点。可以列得延迟钦定 DP:

第三维 S \in [-nV, k],故复杂度 O(n^3 V) 无法通过。

考虑微元贡献法 a_r-a_l=\sum\limits_{i=l+1}^r (a_i-a_{i-1}),令 i 决策后立刻计算微元 a_i-a_{i-1} 的贡献。

令 S'=S+x(a_i-a_{i-1}),再转移到 f_{i,x',S'} 只需保留 S' \ge 0 的部分即可。

复杂度 O(n^2 k) 足以通过。代码。

:::::

P14364 [CSP-S 2025] 员工招聘

给定 n 和长为 n 的 01 串 S。考虑 1\sim n 的排列 p_i,初始有变量 x=0,依次对 i=1,2,\cdots,n 执行:

  • 若 S_i=0 或 x \ge c_{p_i},令 x\gets x+1。

求最终 x \le n-m 的 p_i 数目。取模 998244353。

:::::success[解法一]

考虑从左到右填入的计数顺序。

注意到 c_i \le x 的 i 行为相同,c_i>x 的 i 行为相同,且转化具有单向性,故设计延迟钦定 DP:

注意到 \sum \text{cnt}=n,故 z 的总枚举次数正确,复杂度 O(n^3)。注意常数问题,代码。

:::::

:::::success[解法二]

取集合 U=\{i \mid S_i=1\},设 S \subseteq U 为 x 不变的位置集合,只要 |S|\ge m。对位置 i 分讨:

限制 c_i > * 是困难的,将其容斥为 1-[c_i \le *]。钦定 T \subseteq S 满足:

容斥系数 (-1)^{|T|}。

这里 (T,S \setminus T, U \setminus S) 构成 U 的划分。对划分情况进行 DP:

复杂度 O(n^3)。代码。

带着容斥系数 DP,将 (-1)^v 放到 DP 值里面就是第一篇题解的做法了。

:::::