延迟钦定贡献 DP
stripe_python · · 个人记录
AT_mujin_pc_2018_f チーム分け
现有
n 个元素,你需要将每个元素分到某组中,要求i 所在组的大小不超过a_i 。求合法分组方案数,对998244353 取模。
::::::success[题解]
单组限制只关心
在加入
- 设
f_{i,j} 为满足下列条件的合法分组方案数。- 仅考虑
1 \sim i ,但不需决定1 \sim i 的全部归属。 -
- 仅考虑
- 转移时仅有两种决策:
- 第
i 个元素无归属,转移f_{i,j} \to f_{i+1,j+1} 。 - 第
i 个元素新开一组,并从j 个未决策元素中取出若干加入这一组。枚举k \in [0,a_i) ,转移f_{i,j} \times \binom{j}{k} \to f_{i+1,j-k} 。
- 第
- DP 初值为
f_{0,0}=1 。 - 答案为
f_{n,0} 。
复杂度
:::::info[延迟钦定 DP]
本题通过延迟钦定的组合意义,解决了贡献系数无法计算的问题。我们将本题的模型进行抽象:
- 对每个组合对象决策某种属性。
- 将决策划分为两部分,确定部分不会影响贡献系数,待定部分还会影响贡献系数。待定到确定的转化是单向的。
- 确定部分等价,待定部分的决策等价。
- 考虑在 DP 状态中记录待定部分的信息,每个对象的决策变为,进入待定部分或进行确定性决策。在确定性决策时,处理待定部分的贡献。
:::::
::::::
P7154 [USACO20DEC] Sleeping Cows P
现有
n 个左部点a_i 和n 个右部点b_i 。若a_i \le b_j 则连边i \to j 。称二分图的一个匹配是极大的,当且仅当任意失配的左部点无法与失配的右部点匹配。对极大匹配计数,取模
10^9+7 。
:::::success[题解]
刻画极大匹配的性质:
- 若左部点
i 失配,则a_i \le b_j 的j 必须匹配。 - 若右部点
j 失配,则a_i \le b_j 的i 必须匹配。
我们将
为叙述简便,下文称最终失配的点被放弃,最终得到匹配,但当前失配的点被保留。
考虑延迟钦定 DP:
- 设
f_{0/1,i,j} 为满足下列条件时,合法匹配的数目:- 仅考虑
x_1 \sim x_i 。 - 当前有
j 个保留的左部点失配。 - 指示变量
0/1 表示,x_1 \sim x_i 中是否存在被放弃的左部点。
- 仅考虑
- 加入
x_{i+1} 时对决策进行讨论:- 若
i+1 是左部点:- 放弃
x_{i+1} ,转移f_{0/1,i,j} \to f_{1,i+1,j} 。 - 保留
x_{i+1} ,转移f_{0/1,i,j} \to f_{0/1,i+1,j+1} 。
- 放弃
- 若
i+1 是右部点:- 令
x_{i+1} 匹配某个左部点,转移j \times f_{0/1,i,j} \to f_{0/1,i,j-1} 。 - 放弃
x_{i+1} ,要求过去不存在放弃的左部点,转移f_{0,i,j} \to f_{0,i+1,j} 。
- 令
- 若
- DP 初值为
f_{0,0,0}=1 。 - 答案为
f_{0/1,2n,0} 。
复杂度
:::::
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[题解]
考虑建
将
考虑延迟钦定配对 DP:
-
设
f_{i,j} 为满足下列条件时,合法匹配的权值和:- 仅考虑
x_1 \sim x_i 。 - 恰好匹配了
j 对点。
- 仅考虑
-
注意到左右部点的地位相同,直接考察决策:
-
令
x_{i+1} 暂时失配,转移f_{i,j} \to f_{i+1,j} 。 -
令
x_{i+1} 与前缀中某个数匹配。预处理c_i 为x_1 \sim x_i 中与x_{i+1} 不同部的点数,转移f_{i,j} \times x_{i+1} \times (c_i-j) \to f_{i+1,j+1} 。系数
x_{i+1} 是权值,c_i-j 是选法数。
-
-
DP 初值为
f_{1,0}=1 。 -
答案为
f_{2n,n} ,除以n! 得到期望。
复杂度
:::::
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[题解]
设第
直接对着 DP 需要记录
若
将
将
- 设
f_{i,x,y,s} 为满足如下条件时,完美匹配的方案数:- 仅考虑
b_1 \sim b_i 。 - 当前有
x 个左部点失配,y 个右部点失配。 - 已匹配边的边权和为
s 。
- 仅考虑
- 转移时根据点的类型分讨。下面以
b_{i+1} 是左部点为例说明,右部点转移同理。- 令
b_{i+1} 暂时失配,转移f_{i,x,y,s} \to f_{i+1,x+1,y,s} 。 - 令
b_{i+1} 与之前某个右部点匹配,转移f_{i,x,y,s} \times y \to f_{i+1,x,y-1,s+b_{i+1}} 。
- 令
- DP 初值为
f_{0,0,0,0}=1 。 - 答案为
\sum \limits_{j=k}^{\binom{n}{2}} f_{2n,0,0,j} 。
不难发现,由于
:::::
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[题解]
结论 设
证明 根据排序网络的 01 原理,任取阈值
设
只要
下面对
-
设
f_{i,j} 为满足下列条件的合法方案数:- 仅考虑标号为
1\sim i 的左右部点。 - 恰好匹配了
j 对点。
- 仅考虑标号为
-
转移
f_{i-1,j} \to f_{i,j'} ,加入左右部点i ,分讨匹配方式:- 将两点都加入待定部分,转移
f_{i-1,j} \to f_{i,j} 。 - 将左部点
i 配给待定右部点,令右部点待定,转移q \times f_{i-1,j} \to f_{i,j+1} 。系数q=i-1-j 为上一步的失配点对数。 - 将右部点
i 配给待定左部点,令左部点待定,转移q \times f_{i-1,j} \to f_{i,j+1} 。 - 将左右部点
i 直接匹配,转移f_{i-1,j} \to f_{i,j+1} 。 - 将左部点
i 配给待定右部点,同时将右部点i 配给待定左部点,转移q^2 \times f_{i-1,j}\to f_{i,j+2} 。
前
i 个位置中,有j 个位置的数字\le i ,那么q_i=i-j 。只保留q_i \le k 的状态即可满足约束。 - 将两点都加入待定部分,转移
-
DP 初值为
f_{0,0}=1 。 -
答案为
f_{n,n} 。
复杂度
:::::
CF626F Group Projects
给定长为
n 的序列a_i 。你需要将n 个有标号元素划分为若干无标号组。组内权值定义为\max-\min ,要求总权值\le k 。求方案数,取模10^9+7 。
:::::success[题解]
将
- 设
f_{i,x,S} 为满足下列条件的合法方案数:- 仅考虑
a_1 \sim a_i 。 - 现有
x 个未确定\max 的组。 - 当前可确定的权值和为
S 。即确定部分权值和,加上待定部分-\min 的和。
- 仅考虑
- 转移
f_{i-1,x,S} \to f_{i,x',S'} ,讨论a_i 的归属:- 钦定为某个待定组的
\max ,移除待定部分,转移x \times f_{i-1,x,S} \to f_{i,x-1,S+a_i} 。 - 加入某个待定组,转移
x \times f_{i-1,x,S} \to f_{i,x,S} 。 - 新开一个确定组,转移
f_{i-1,x,S} \to f_{i,x,S} 。 - 新开一个待定组,转移
f_{i-1,x,S} \to f_{i,x+1,S-a_i} 。
- 钦定为某个待定组的
- DP 初值为
f_{0,0,0}=1 。 - 答案为
\sum \limits_{S=0}^k f_{n,0,S} 。
第三维
考虑微元贡献法
令
复杂度
:::::
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[解法一]
考虑从左到右填入的计数顺序。
注意到
-
设
f_{i,x,y} 为满足下列条件的合法方案数:- 仅决策
p_1\sim p_i 。 -
- 前缀
1\sim i 中预留y 个c_i>x 的位置,这些位置的具体值待定。
- 仅决策
-
转移令
f_{i-1,x,y} \to f_{i,x',y'} 。对S_i 分讨:-
若
S_i=0 ,必然有x'=x+1 。此时c_i=x' 的i 移除待定部分,枚举原待定部分c_i=x' 的数目z \in [0,y] ,则y' \gets y-z 。贡献系数为:- 选出
z 个数在原待定部分,方案数\binom{\text{cnt}_{x+1}}{z} \binom{y}{z} 。 - 令
z 个数任意排列,方案数z! 。
设
a_x 为c_i \le x 的i 的数目。讨论c_{p_i} 与x' 的大小关系:-
钦定
c_{p_i} \le x' ,已用掉(i-1)-(y-z) 个\le x' 的数,可用的数目为a_{x+1}-(i-1-(y-z)) 。转移
\binom{\text{cnt}_{x+1}}{z} \binom{y}{z} z!(a_{x+1}-(i-1-y+z))f_{i-1,x,y} \to f_{i,x+1,y-z} 。 -
钦定
c_{p_i}>x' ,将p_i 扔进待定部分,转移\binom{\text{cnt}_{x+1}}{z} \binom{y}{z}z! f_{i-1,x,y} \to f_{i,x+1,y-z+1} 。
- 选出
-
若
S_i=1 ,只要讨论c_{p_i} 与x 的大小关系。-
若
c_{p_i} \le x ,则x'=x+1 。枚举z 个i 移出待定部分,贡献系数同理。已用掉(i-1)-y 个\le x 的数,可用数目a_x-(i-1-y) 。转移
\binom{\text{cnt}_{x+1}}{z} \binom{y}{z} z!(a_x-(i-1-y)) f_{i-1,x,y} \to f_{i,x+1,y-z} 。 -
若
c_{p_i} >x ,则x'=x ,将p_i 扔进待定部分,直接转移f_{i-1,x,y} \to f_{i,x,y+1} 。
-
-
-
DP 初值为
f_{0,0,0}=1 。 -
答案为
\sum \limits_{x=0}^{n-m} (n-a_x)!f_{n,x,n-a_x} ,系数(n-a_x)! 表示令待定部分随意排列。
注意到
:::::
:::::success[解法二]
取集合
- 若
i \in S ,要求c_i>\sum \limits_{j < i} [j \notin S] 。 - 若
i \notin U \setminus S ,要求c_i \le \sum\limits_{j<i} [j \notin S] 。
限制
- 若
i \in T ,要求c_i \le \sum\limits_{j<i} [j \notin S] 。 - 若
i \in S \setminus T ,c_i 无限制。
容斥系数
这里
-
设
f_{i,u,v} 为满足下列情况的合法方案数:- 仅考虑
1 \sim i 位置。 -
- 仅考虑
T 和U \setminus S 位置上填入的数。
- 仅考虑
-
转移时逐个加
i ,令f_{i-1,u,v} \to f_{i,u',v'} 。-
若
S_i=0 则i\notin S ,转移f_{i-1,u,v} \to f_{i,u,v} 。 -
若
S_i=1 ,此时x=i-1-u 。剩余\le x 的点数为q=\sum \limits_{i=1}^n [c_i \le x]-|T|-|U \setminus S| 。其中
|T|=v ,|U\setminus S|=|U|-|S|=\sum \limits_{j <i} [S_j=1]-u 。容易预处理后算出转移系数q 。- 令
i 加入U \setminus S ,需要c_i \le x ,转移q \times f_{i-1,u,v} \to f_{i,u,v} 。 - 令
i 加入T ,需要c_i \le x ,转移q \times f_{i-1,u,v} \to f_{i,u+1,v+1} 。 - 令
i 加入S \setminus T ,无限制,转移f_{i-1,u,v} \to f_{i,u+1,v} 。
- 令
-
-
DP 初值为
f_{0,0,0}=1 。 -
算答案时枚举
(u,v) 满足u \ge m 。容斥系数(-1)^v ,剩余|S \setminus T| 个位置任意排列,方案数\left(n-|U|+u-v\right)! 。则答案式为\sum_{u=m}^n \sum_{v=0}^u (-1)^v\left(n-|U|+u-v\right)! f_{n,u,v}
复杂度
带着容斥系数 DP,将
:::::