计数题

这几天琢磨其他东西，差点忘了自己还有省选没有参加（虽然参不参加都进不了队），但还是想认真对待一下这次省选

[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)$，能构造出的不合法的情况的方案数：

答案就是总的方案数减去不合法的方案数。

[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$，从刚刚我所说的能看出来它的转移是不具有后效性的。有如下方程

这里有一个 $+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;
}

[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)$。答案就是

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)$。

【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$ 个空隙。

同时注意到当 $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;
}

最后的答案就是

第二步转移使用后缀和即可。给出核心代码加以理解。

// 初始化第 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$ 的方案数。有如下转移：

最终答案就是：

注意当 $\frac{sum}{2}$ 为奇数时无解。时间复杂度在 $O(n^2 \cdot \sum w_i)$。

[CSP-S 2025] 员工招聘

排列计数 DP+贡献延后计算

设 $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$ 的人可以通过面试，有如下转移

选择 $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)$。有如下转移：

如果 $s_{i+1}=0$，按照上面的情况讨论即可，如果选择 $c>j+1$，有如下转移：

若选择 $c \le j+1$，有如下转移：

最终答案就是枚举不通过人数到 $n-m$。

如果难以理解可以看代码

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 是“走到哪，填到哪，算到哪”。但在本题中：

1. 只占坑，不结账（延后）： 当某天面试难度低（$s=1$）时且选择了能够通过的人，我们不急着决定今天具体录用谁，而是把这一天当成一个“空白名额”积攒下来，此时方案数直接继承（即不乘任何组合数，延后贡献计算）。
2. 触碰底线，集中清算（兑现）： 当不通过人数增加（$j \gets j+1$）时，那些忍耐度为 $c=j+1$ 的人到了必须被安排的生死线。此时我们才回溯，从之前积攒的“空白名额”中抽出几个，把这批人填进去。这时才一次性乘上对应的组合数与排列数，完成历史贡献的集中清算。

这就是贡献延后计算：先把空位留着，等特定元素的限制条件被触发时，再统一计算它们填入空位的排列方案。

P17224 [Math×Girl²] 搬家

挖掘性质+组合计数

题目中的 $N$ 和 $M$ 这里写为 $n$ 和 $m$。

对于一组确定的大小，考虑怎么选是最优的，不妨把大小为 $2$ 的物品（假设是第 $k$ 个）看成两个大小为 $1$ 且价值为 $\frac{3^{n-k}}{2}$ 的物品，只不过这两个物品必须都选或者都不选。注意到 $3^{n-k+1} > \frac{3^{n-k}}{2} > 3^{n-k-1}$，因此这两个物品的相对价值较之前并没有改变，而现在所有物品的大小都是 $1$，价值按照编号递减，因此最优的选法应当是按编号从小到大扫描，能装就装，不能装就跳过。
我们将结果视作三种情况：

1. 刚好选的是一段前缀，箱子没有空余位置。
2. 选的是一段前缀，而前缀后面紧邻的物品大小为 $2$，这个物品后面的大小为 $1$ 的物品被选上。或者前缀后的物品大小都是 $2$，导致箱子空出一个位置。
3. 全部被选上且箱子有剩余位置。

考虑对于题目中的打包机何时会选择最优的并计算方案数。

如果最优结果是第一种，则需要保证前缀内的大小之和为 $m$。若前缀长度为 $k$，先为这 $k$ 个元素分配 $1$ 的大小，再选 $m-k$ 个物品使其大小增加 $1$，方案数是 $\binom{k}{m-k}$，因此也有 $k \le m \le 2k$。当 $k=m$ 时，前缀后的所有物品大小随意，方案数是 $2^{n-k}$，否则前缀后的物品必须大小为 $2$。

如果最优结果是第二种，需要保证前缀大小之和为 $m-1$，根据上一条可知有 $\binom{k}{m-1-k}$ 种方案，这里有 $k+1 \le m \le 2k+1$。我们仔细讨论一下后面的物品的大小，当 $k=m-1$ 时，第 $k+1$ 个物品大小必须是 $2$，后面的随意，有 $2^{n-k-1}$ 种方案。当 $k \ne m-1$ 时，第 $k+1$ 个物品大小必须是 $2$，后面的物品需要有一个大小是 $1$，其他都是 $2$，或者全是 $2$，有 $n-k$ 种方案。

如果最优结果是第三种，需要先保证 $m>n$，枚举所有物品的大小总和 $k$ 从 $n$ 到 $ \min \left \{2n,m-1\right \}$，不能枚举到 $m$，否则和第一种情况是一样的。这样的方案有 $\sum \binom{n}{k-n}$。

处理阶乘逆元的时候利用 $n!$ 的逆元以 $O(n)$ 的复杂度求出所有阶乘的逆元，时间复杂度可以做到 $O(n)$。

前面的几道题的记录我都当作题解去写，后面只会记录核心思路，边界细节什么的不再描述。

CF2256D A Ribbon for Tomorrow

性质转化+组合计数

把原字符串的相邻且相同的数合并，形成若干连续段，设 $(a_i,b_i)$ 表示第 $i$ 个连续段内的数都是 $a_i$，且有 $b_i$ 个数，这里 $a_i \in \{ 0,1 \}$。例如 001010 可以表示为 00|1|0|1|0。

因此 $a$ 数组只能是 ...01010101...，注意到任意翻转操作无法改变连续段的结构（也就是无法改变 $a_i$），只能改变段内数字的个数（也就是只能改变 $b_i$），通过若干次翻转可以发现，所有合法的正整数段长分配都能做到。

我们规定一些变量，$c_0$ 表示原字符串当中 $0$ 的个数，$c_1$ 表示 $1$ 的个数。$r_0$ 表示 $0$ 的连续段的个数，$r_1$ 表示 $1$ 的连续段的个数。

于是问题转换成了：把 $c_1$ 个 $1$ 分成 $r_1$ 组，每组至少有一个，把 $c_0$ 个 $0$ 分成 $r_0$ 组，每组至少有一个，求方案数。

利用插板法解决：

时间复杂度可以做到 $O(\sum n)$。

[ARC223C] Whole Product of Pairwise Distances

挖掘性质+排列计数

注意到若有两数满足 $a_i \equiv a_j \pmod{n}$，则有 $|a_i-a_j| \mod{n}=0$。又注意到对于任意排列的答案都是一样的，我们对原数列进行排序就可以去掉绝对值，而又有 $(a_i-a_j) \mod{n} =(a_i \mod{n} -a_j \mod{n}) \mod n$，所以我们取 $p_i \gets a_i \mod{n}$。若只要有两数一样，答案就是 $0$。否则原序列就是 $0$ ~ $n-1$ 的排列。考虑如何计算这个答案。考虑转化计数，枚举差值，有如下

$\text{inv(p)}$ 表示排列的逆序对个数，$O(n \log n)$ 即可做到，其中 $\log n$ 是用树状数组求逆序对个数。那么如何做到 $O(n)$。我们不需要关注有多少对逆序对，我们只需要关注逆序对个数的奇偶性。

把排列看作若干 $i \to p_i$ 的有向边，构成若干环，若有 $c$ 个环，对于其中一个环，如果有 $k$ 个元素，可以表示成 $k-1$ 次元素交换，而对于任意一次元素交换，都会改变排列逆序对个数的奇偶性，可以以相邻元素交换为根据，相邻元素交换一次，逆序对个数加 $1$，不相邻的元素交换可以拆成若干次相邻元素交换，能够证明奇偶性改变。因此 $(-1)^{\text{inv}(p)}=(-1)^{n-c}$。

[ARC223E] Yin-Yang Two Bits Insertion

性质转化+DP

题目问是否能通过若干次在 $A$ 中插入两个与插入位置两侧相反的值使得 $A=B$，考虑插入后什么东西没有变或是什么东西是一定的。令 $c_i=A_i \oplus A_{i+1}$，$d_i=B_i \oplus B_{i+1}$，一次操作后 $c_i$ 变成 $(1,c_i,1)$。问最终是否能使 $c=d$ 且 $A_1=B_1$。注意到 $0$ 的数量始终不变，因此若两数组 $0$ 的数量不一样一定不行。我们根据 $0$ 的位置分段，令新数组 $x_i$ 和 $y_i$，$x_i$ 表示 $c$ 数组中第 $i-1$ 个 $0$ 与第 $i$ 个 $0$ 之间 $1$ 的个数。$y_i$ 同样表示 $d_i$ 的分段数组。
例如（下标从 $1$ 开始）：

则：

因此有操作一：$x_i \gets x_i+2 \quad (x_i > 0)$，操作二：$(x_i,x_{i+1}) \gets (x_i+1,x_{i+1}+1)$。
注意到对于同一位置，操作二执行 $0$、$1$ 或 $2$ 次是有意义的，之后则都可以用操作一替代。 因此题目最终转化成了：对数组 $x$ 执行若干次操作二，使得 $0 < x_i \le y_i$ 且 $x_i$ 与 $y_i$ 共奇偶，或者 $x_i=y_i=0$

令 $dp_{i,j}$ 表示处理到了 $x_{i}$，并在位置 $i$ 执行了 $j$ 次操作二，此时是否合法，$j \in \{ 0,1,2\}$，有如下转移：

当满足如下时，$\operatorname{jud}_{i,j,k}=1$，否则 $\operatorname{jud}_{i,j,k}=0$。

时间复杂度是 $O(n)$ 的。

[ARC107D] Number of Multisets

计数 DP

设 $dp_{i,j}$ 表示用了 $i$ 个数，和为 $j$ 的方案数，因为转移过程中 $i$ 和 $j$ 只能是整数。若 $dp_{i,j}$ 的 Multiset 里面含有 $1$，则可以从 $dp_{i-1,j-1}$ 转移而来，若没有呢？注意到将 Multiset 里的所有数乘以 $2$ 后，每个数仍然可以表示为 $\frac{1}{2^i}$，总和变为了 $2j$，又注意到这样的集合与 $dp_{i,2j}$ 构成双射。因此有如下

可以 $O(nk)$ 做到，这里 $2j \le i$ 是因为当 $2j > i$ 时，Multiset 里必然包含 $1$。

[ABC217F] Make Pair

区间 DP

类似括号序列的 $\text{Plus}$ 版，考虑能否区间 DP 解决，设 $dp_{i,j}$ 表示区间 $[i,j]$ 内可以有多少种离开队列的情况。

1. $i$ 与 $j$ 是有关系，因此 $dp_{i,j} \gets dp_{i+1,j-1}$。
2. 考虑枚举 $k$，区间 $[i,k]$ 内的离队情况数与 $[k+1,j]$ 的离队方案数综合一下，但是为了不重复计数，我们要求其中一个区间不能是若干合法区间的合并，不妨要求前面这个区间，即必须做到 $i$ 和 $k$ 有关系。因此有如下： $$ dp_{i,j} \gets dp_{i+1,k-1} \cdot dp_{k+1,j} \cdot \binom{\frac{j-i+1}{2}}{\frac{j-k}{2}} $$

这里可以 $O(n^3)$ 做到。

[ABC252G] Pre-Order

区间 DP

P17284 「IXOI R2」想不出来

挖掘性质+计数 DP

考虑最终生成的序列有什么性质，发现若最终序列里有一个位置上的数大于 $1$，其左右两边必须是空位，若有一段区间是连续的 $1$，则表明该区间未被操作，因为该区间未被操作，就使得该区间左右两边的操作被隔离开。形式化地，定义前缀和数组 $s_i=\sum_{j=1}^{i} p_j$，则一个序列被认为是可被生成的充要条件是：

对于序列中所有两个连续的大于零的数 $p_i, p_{i+1}$，满足 $p_i=p_{i+1}=1, s_i=i$。

考虑 DP，设 $f_{i,j}$ 表示处理到了第 $i$ 个数，第 $i$ 个数是 $0$ 且总和为 $j$ 时的权值和，同样地，$g_{i,j}$ 要求 $p_i=1$，$h_{i,j}$ 要求 $p_i \ge 2$。

对于 $f_{i,j}$，由于第 $i$ 个数贡献的是 $x_i^0=1$，因此有

对于 $g_{i,j}$，前一个数只能是 $0$ 或 $1$，当前一个数为 $1$ 时，需要保证 $i=j$，因此有

对于 $h_{i,j}$，前一个数只能是 $0$，当 $p_i=2$ 时，可以从 $f_{i-1,j-2}$ 转移过来，当 $p_i > 2$ 时，可以从 $h_{i,j-1}$ 转移过来，因此有

最后答案就是 $f_{n,n}+g_{n,n}+h_{n,n}$。时间复杂度可以做到 $O(n^2)$ 。

[ABC284G] Only Once