这几天琢磨其他东西，差点忘了自己还有省选没有参加（虽然参不参加都进不了队），但还是想认真对待一下这次省选，就认真做几道题目吧。
P14636 [NOIP2025] 清仓甩卖
性质转化+计数
考虑什么时候不合法，我们可以把 $w_i=2$ 的物品看作两个定价为 $1$，原价为 $\frac{a_i}{2}$ 的物品，只不过这两个物品必须捆绑购买，这样我们所有的物品的定价就是 $1$ 元，我们只需要买原价前 $m$ 大的物品即可（注意到 $\frac{a_i}{2}$ 就是这个原物品的性价比，因此小 R 的排序方式与此等同），问题就在如果第 $m$ 个物品与第 $m+1$ 个物品是必须捆绑购买的，小 R 会放弃第 $m$ 个物品，向后寻找一个不被捆绑的物品（不妨设其为第 $k$ 个物品，$k$ 可能不存在）进行购买，如果此时第 $m-1$ 个物品是不被捆绑的，且 $v_{m-1}+v_{k} < v_m+v_{m+1}$（这里用 $v_i$ 表示按如上情景下第 $i$ 件物品的原价），小 R 的选法就不是最优的，形式化的如下：
小 R 在剩余最后 $2$ 元的时候，此时有 $a_i>\frac{a_j}{2}>a_k$ 且 $a_j>a_i+a_k$，小 R 的选择不是最优的
我们可以计算不合法的方案数，我们不妨枚举每一对 $(i,j)$，使得 $a_i>\frac{a_j}{2}$ 且 $a_j>a_i$，再去寻找「第一个」符合条件的 $k$（第一个满足 $a_k<a_j-a_i$ 的 $k$），找 $k$ 的过程使用双指针可以做到 $O(n^2)$，容易发现其位置满足
.....j....i...k...
我们需要计算一对 $(i,j)$ 能够造出多上个不合法的方案
- $[1,j-1]$ 中的物品一定会被买。
- $[j+1,i-1]$ 中定价为 $1$ 的物品一定会被买到，定价为 $2$ 的则不会。
在这两段，我们必须花掉 $m-2$ 元。
- $[i+1,k-1]$ 中的物品不会被买到，且定价必须是 $2$。
- $[k,n]$ 中的物品不会被买到，定价随意（注意这里 $w_k$ 的取值也是随意的）。
我们只需计算 $m-2$ 用于分配的方案数，第一段每个先给保底 $1$ 元，还剩 $m-2-(j-1)=m-j-1$ 元，接着这些钱要分配给第一段中 $w=2$ 的物品和第二段中 $w=1$ 的物品各 $1$ 元。方案数是 $\binom{i-2}{m-j-1}$。第三段不用考虑。因为 $w_k$ 的取值也是随意的，所以第四段的方案数是 $2^{n-k+1}$。对于一组 $(i,j)$，能构造出的不合法的情况的方案数：
$$ \binom{i-2}{m-j-1}\cdot 2^{n-k+1} $$答案就是总的方案数减去不合法的方案数。
$$ Ans=2^n-\sum_{(i,j,k)}\binom{i-2}{m-j-1}\cdot 2^{n-k+1} $$P10744 [SEERC 2020] Modulo Permutations
挖掘性质+排列DP+DP优化
首先注意到，当 $p_i<p_{i+1}$ 时，$p_i \mod p_{i+1}=p_{i+1}$，因此当 $p_i>2$ 时，接在它后面的数必须比它小，因此不难发现，合法的排列由两个结尾分别是 $1$ 和 $2$ 的递降的链构成。考虑 DP,考虑从大往小填充数字，令 $dp_{i,j}$ 表示以 $i$ 和 $j$ 结尾时的方案数，其中 $i<j$。则有如下 $O(n^2)$ 的转移，初始 $dp_{n-1,n}=1$。
考虑优化 DP，注意到方程第二维只从原先更高的转移过来，因此我们把第二维单独摘出来，令 $dp_i$ 表示两个链的结尾最大是 $i$，从刚刚我所说的能看出来它的转移是不具有后效性的。有如下方程
$$ dp_i=1+\sum_{j \in [i+1,n],j \mod (i-1)\le 2} dp_j $$这里有一个 $+1$，意思是还有一个方案没有被考虑，两个链分别是
n,n-1,n-2,...,i+1
i
我们找这个 $j$ 的复杂度是 $O(\frac{n}{i})$，从如下数字中找
- $((i-1)+0) \cdot k$
- $((i-1)+1) \cdot k$
- $((i-1)+2) \cdot k$
这样总的复杂度就是调和级数，$O(n \ln n)$。因为是一个环，最后的答案就是 $n \cdot dp_2$.优化部分不是很好想，给出核心代码加以理解。
for (int m = n - 1; m >= 1; --m) {
long long cur_sum = 1;
if (m >= 3) {
for (int k = 1; k * m <= n; ++k) {
int base = k * m;
// j 必须大于 m + 1
if (base > m + 1) cur_sum =(cur_sum + f[base]) % MOD;
if (base + 1 <= n && base + 1 >m + 1) cur_sum = (cur_sum + [base + 1]) % MOD;
if (base + 2 <= n && base + 2 >m + 1) cur_sum = (cur_sum + [base + 2]) % MOD;
}
}
else {
// 当 m = 1 或 2 时，任何数 mod 它必然 <= 2，直接累加所有有效的 j
for (int j = m + 2; j <= n; ++j) {
cur_sum = (cur_sum + f[j]) %MOD;
}
}
f[m + 1] = cur_sum;
}
P10741 [SEERC 2020] Fence Job
性质转化+计数DP
题目等同于让某一个数向周围比它大的扩散，问可以产生多少种排列。我们先预处理出来每个数可以覆盖的范围，对于 $h_i$，他可以覆盖 $[l_i,r_i]$ 下标内的所有数。我们在一个空的排列上依次填数即可，考虑 DP，设 $dp_{i,j}$ 表示处理到排列的第 $i$ 个位置，要填入 $h_j$ 的方案数。前提是保证 $l_j \le i \le r_j$，否则 $dp_{i,j}=0$。同时注意到产生的新排列的每个数在原排列中的下标是单调不降的。于是
这一步可以用前缀和实现，复杂度是 $O(n^2)$。答案就是
$$ Ans=\sum_{i=1}^{n}dp_{n,i} $$AT_dp_t Permutation
排列计数DP+插入法技巧
因为给了相邻两项的大小关系，没有具体数值的要求，所以考虑插入法（https://www.luogu.com.cn/article/xt2szowt），就是对待填入数字在已知排列中的排名进行 DP，设 $dp_{i,j}$ 表示考虑到第 $i$ 个位置，第个位置上的数在前 $i$ 个数当中排名为 $j$。有如下转移
关于初始化，$dp_{1,1}=1$，这是因为我们只考虑相对大小，不对该位置上的具体数值进行讨论，因此只有一种情况，对方程进行一下前缀和优化就能做到 $O(n^2)$。
[ABC282G] Similar Permutation
排列计数DP+插入法技巧
这道题下相当于上一道的二维的加强版，令 $dp_{i,j,k,p}$ 表示处理到第 $i$ 个元素中，$A_i$ 排名为 $j$，$B_i$ 排名为 $k$，有 $p$ 处满足限制。初始时 $dp_{1,1,1,0}=1$，有 $O(n^5k)$ 转移。
这里用二维前缀和即可做到 $O(n^3k)$。
$$ sum_{i,j,k,p}=\sum_{x=1}^{j} \sum_{y=1}^{k} dp_{i,x,y,p} $$P14568 【MX-S12-T3】排列
排列计数DP+插入法技巧
这道题我认为还是很难理解的。对于排列中的数字，不仅有前缀的限制，也有后缀的限制，传统的像前两道题的 DP 状态只能解决一个方向，我们干脆对“位置”进行放置，意思就是我们按照位置的顺序（第 $1$ 个数、第 $2$ 个数 $\dots$ 第 $n$ 个数），依次把它们放进一个“按照值从小到大排序的虚空序列”里。设 $dp_{i,j}$ 表示安排了前 $i$ 个位置，为后来的位置留下了 $j$ 个“合法”（不影响前 $i$ 个位置的合法性）的空隙。
对于 $op_i \in { 0,1 } $，我们放置的第 $i$ 个位置必须在所留下的空隙的最左面或最右面，放下的同时也会产生两个空隙，后来的位置可以随便插不会影响第 $i$ 个位置
对于 $op_i \in { 2,3 } $，我们可以把第 $i$ 个位置插入到任意一个空隙中，但对后来的位置，其左边或右边的所有空隙不再合法。因此他会从 $dp_{i-1,\ge j}$ 的状态中转移过来。这里有一个上限是 $i$，因为 $i-1$ 个位置最多产生 $i$ 个空隙。
$$ dp_{i,j}=\sum_{k=j}^{i} dp_{i-1,k} $$同时注意到当 $op_i=2/3$ 时，后面不能再出现 $op_j=0/1$。（注：$0$ 对应 $2$，$1$ 对应 $3$），这里只需特判一下。
// 逻辑矛盾预检：一旦出现后缀最值(2/3)，未来不可能出现前缀最值(0/1)
bool flag2 = false, flag3 = false;
for (int i = 1; i <= n; i++) {
if (op[i] == 0 && flag2) { cout << 0 << endl; return 0; }
if (op[i] == 1 && flag3) { cout << 0 << endl; return 0; }
if (op[i] == 2) flag2 = true;
if (op[i] == 3) flag3 = true;
}
最后的答案就是
$$ Ans=\sum_{j=1}^{n+1}dp_{n,j} $$第二步转移使用后缀和即可。给出核心代码加以理解。
// 初始化第 1 个元素
if (op[1] == 0 || op[1] == 1) {
dp[1][2] = 1; // 没有任何限制，左右两侧的2 个空隙均合法
} else {
dp[1][1] = 1; // 封杀了一侧，只剩下 1 合法空隙
}
// 状态转移
for (int i = 2; i <= n; i++) {
if (op[i] == 0 || op[i] == 1) {
// 必然插在极值端，合法空隙增加 1 个(j 从 j-1 转移而来)
// 上一步最多有 i 个空隙，所以这一步多产生 i+1 个空隙
for (int j = 2; j <= i + 1; j++) {
dp[i][j] = dp[i - 1][j - 1];
}
}
else {
// 可以插在任意合法的空隙，但会封杀左或右侧
// 导致合法空隙缩小为 j (需要上一层>= j 的状态累加)
long long suffix_sum = 0;
// 上一步最多只有 i 个空隙，直接从 i逆序求后缀和即可，清晰明了！
for (int j = i; j >= 1; j--) {
suffix_sum = (suffix_sum + dp[i- 1][j]) % MOD;
dp[i][j] = suffix_sum;
}
}
}
// 最终答案统计
// n 个位置全部处理完毕后，不论剩下多少个合法隙，每一种终点状态都代表一种完美的排列方案
long long ans = 0;
for (int j = 1; j <= n + 1; j++) {
ans = (ans + dp[n][j]) % MOD;
}
[AGC054B] Greedy Division
性质转化+排列计数DP+切换计数对象
考虑最终两人手上的排列都是什么情况，如果一人手中的数集是 $S$，另一人手中的数集则是 $S’$。则对于唯一的 $S$，可以构造出的排列数是 $|S|! \cdot (n-|S|)!$。
对于两个 $S$ 和 $S’$，对两数集进行排列，重新排列后的两数集按照题目中的规则可唯一合并为一个排列，即：
$$ \left \{ S_{一种排列} ,S'_{一种排列} \right \} \Leftrightarrow \left \{ W_{一种合法的排列} \right \} $$
可以发现对于一中选择 $S$，能产生的方案数只与大小有关。考虑 DP，设 $dp_{i,j,k}$ 表示对于前 $i$ 个数，选了 $j$ 个数，总和为 $k$ 的方案数。有如下转移：
$$ dp_{i,j,k}=dp_{i-1,j-1,k-w_i}+dp_{i-1,j,k} $$最终答案就是：
$$ Ans=\sum_{i=1}^{n} dp_{n,i,\frac{sum}{2}} \cdot i! \cdot (n-i)! $$注意当 $\frac{sum}{2}$ 为奇数时无解。时间复杂度在 $O(n^2 \cdot \sum w_i)$。
P14364 [CSP-S 2025] 员工招聘
在这里给出两种方法
贡献延后计算 DP
贡献延后计算是一个常见的 trick，设 $dp_{i,j,k}$ 表示处理到第 $i$ 天，有 $j$ 个人不通过，⌈钦定⌋ 了 $k$ 个满足 $c \le j$ 的位置，此时的方案数。这个状态可能比较难以理解，我们只考虑钦定的这 $k$ 个位置造成的方案数，不考虑剩下 $i-k$ 个位置的具体内容。我们规定 $cnt_j$ 表示 $c=j$ 的人数，$sum_j$ 表是 $c \le j$ 的人数，我们考虑向后转移
如果 $s_{i+1}=1$，选择 $c>j$ 的人可以通过面试，有如下转移
$$ dp_{i+1,j,k} \gets dp_{i,j,k} $$选择 $c \le j$ 的则不会通过，考虑怎么转移，此时有 $j+1$ 个人不能通过，枚举前 $i$ 个人当中有 $p$ 个 $c=j+1$，新状态就是 $dp_{i+1,j+1,k+1+p}$.我们需要在原来 $i-k$ 个位置中选出 $p$ 个位置来放置这 $p$ 个 $c=j+1$，即 $\binom{i-k}{p}$，还要从那些 $c=j+1$ 的人当中选出 $p$ 个来填充这些位置，这 $p$ 个人也可以随意排列，方案数是 $\binom{cnt_{j+1}}{p}p!$，再从所有未被钦定的 $c \le j$ 的当中选一个，即 $\binom{sum_j-k}{1}=(sum_{j}-k)$。有如下转移：
$$ dp_{i+1,j+1,k+1+p} \gets \binom{i-k}{p}\binom{cnt_{j+1}}{p}p!(sum_j-k)dp_{i,j,k} $$如果 $s_{i+1}=0$，按照上面的情况讨论即可，如果选择 $c>j+1$，有如下转移：
$$ dp_{i+1,j+1,k+p} \gets \binom{i-k}{p} \binom{cnt_{j+1}}{p}p!dp_{i,j,k} $$若选择 $c \le j+1$，有如下转移：
$$ dp_{i+1,j+1,k+p+1} \gets \binom{i-k}{p} \binom{cnt_{j+1}}{p}p!(sum_{j+1}-p-k)dp_{i,j,k} $$最终答案就是枚举不通过人数到 $n-m$。
$$ Ans=\sum_{i=1}^{n-m} dp_{n,i,sum_i}(n-sum_{i})! $$如果难以理解可以看代码
newdp[0][0]=1;
for(int i=0;i<n;i++){
memcpy(olddp,newdp,sizeof(newdp));
memset(newdp,0,sizeof(newdp));
for(int j=0;j<=i;j++)
for(int k=0;k<=min(sum[j],i);k++){
if(!olddp[j][k]) continue;
if(s[i+1]=='1'){
(newdp[j][k] += olddp[j][k]) %= Mod;
for(int p=0;p<=min(i-k,cnt[j+1]);p++)
(newdp[j+1][k+p+1] += C[i-k][p]*C[cnt[j+1]][p]%Mod*jc[p]%Mod*(sum[j]-k)%Mod*olddp[j][k]) %= Mod;
}
else{
for(int p=0;p<=min(i-k,cnt[j+1]);p++){
//<=j+1
(newdp[j+1][k+p+1] += C[i-k][p]*C[cnt[j+1]][p]%Mod*jc[p]%Mod*olddp[j][k]%Mod*(sum[j+1]-p-k)) %= Mod;
//>j+1
(newdp[j+1][k+p] += C[i-k][p]*C[cnt[j+1]][p]%Mod*jc[p]%Mod*olddp[j][k]) %= Mod;
}
}
}
}
long long ans=0;
for(int i=0;i<=n-m;i++)
(ans += newdp[i][sum[i]]*jc[n-sum[i]]) %= Mod;
这篇题解如何体现 ⌈贡献延后计算⌋？（Gemini 3.1 Pro 总结）
传统的排列 DP 是“走到哪，填到哪，算到哪”。但在本题中：
- 只占坑，不结账（延后）： 当某天面试难度低（$s=1$）时且选择了能够通过的人，我们不急着决定今天具体录用谁，而是把这一天当成一个“空白名额”积攒下来，此时方案数直接继承（即不乘任何组合数，延后贡献计算）。
- 触碰底线，集中清算（兑现）： 当不通过人数增加（$j \gets j+1$）时，那些忍耐度为 $c=j+1$ 的人到了必须被安排的生死线。此时我们才回溯，从之前积攒的“空白名额”中抽出几个，把这批人填进去。这时才一次性乘上对应的组合数与排列数，完成历史贡献的集中清算。
这就是贡献延后计算：先把空位留着，等特定元素的限制条件被触发时，再统一计算它们填入空位的排列方案。