从一道 CSP-J 真题出发：聊聊补集转化与 01 背包计数

题源链接：洛谷 P14360 [CSP-J 2025] 多边形 / polygon

一、背景

在算法竞赛的组合计数专题中，有一类问题特别考验选手的"逆向思维"——它们不问你"满足条件的方案有多少"，而是逼着你先想"不满足条件的方案有多少"。CSP-J 2025 的这道多边形题，就是这类问题的典型代表。

题目场景很生活化：小 R 有

n

n

n 根小木棍，想从中选出若干根拼成一个多边形。多边形的条件是经典的"两边之和大于第三边"的推广：所有木棍长度之和必须严格大于最长木棍的两倍，且至少选

3

3

3 根。

初看之下，这似乎需要枚举所有子集，然后判断每个子集是否满足条件。但当

n

=

5000

n = 5000

n=5000 时，子集数量达到

2

5000

2^{5000}

25000，完全不可行。我们需要一个更聪明的方法——补集转化。

本文就从这道多边形题出发，聊聊补集思想的威力，以及01 背包 DP在组合计数中的经典应用。

二、核心思想

2.1 补集转化：从"正面硬刚"到"曲线救国"

拿到这道题，很多选手的第一直觉可能是：枚举所有子集，检查每个子集是否满足多边形条件。但当

n

n

n 很大时，这是不可能的。

换个角度思考：所有可能的子集有多少个？

2

n

2^n

2n 个（包括空集）。如果我们能快速算出不满足多边形条件的子集数量，那么答案就是：

答案

=

2

n

−

不满足条件的子集数

−

1

\\text{答案} = 2^n – \\text{不满足条件的子集数} – 1

答案=2n−不满足条件的子集数−1

其中

−

1

-1

−1 是去掉空集（空集显然不能拼成多边形）。

这个转化的美妙之处在于：不满足条件的子集有一个统一的特征——设子集中最长木棍为

L

L

L，其余木棍之和为

S

r

e

s

t

S_{rest}

Srest​，则不满足条件意味着

S

r

e

s

t

≤

L

S_{rest} \\leq L

Srest​≤L。这个特征比"满足条件"更容易统计！

我们可以把这个问题想象成筛沙子：

• 所有子集是一堆沙子（$2^n$
• 满足条件的金子混在沙子里
• 直接挑金子很难
• 但我们可以筛掉沙子（不满足条件的子集），剩下的就是金子

2.2 排序 + 枚举最大值：锁定"罪魁祸首"

不满足条件的子集有一个关键特征：它们都有一个"罪魁祸首"——最长的那根木棍。如果我们将木棍按长度升序排序，那么对于排序后的第

i

i

i 根木棍

a

i

a_i

ai​，以它为最长木棍的子集中，其他木棍只能从

a

1

,

a

2

,

…

,

a

i

−

1

a_1, a_2, \\ldots, a_{i-1}

a1​,a2​,…,ai−1​ 中选取。

为什么？因为

a

i

a_i

ai​ 是前

i

i

i 根中最长的（排序后），任何包含

a

j

a_j

aj​（

j

>

i

j > i

j>i）的子集，其最大值都会是

a

j

a_j

aj​ 而非

a

i

a_i

ai​。

这样一来，问题转化为：对于每个

i

i

i，统计从

{

a

1

,

…

,

a

i

−

1

}

\\{a_1, \\ldots, a_{i-1}\\}

{a1​,…,ai−1​} 中选出若干个数，使其和

≤

a

i

\\leq a_i

≤ai​ 的方案数。

排序后的特征：

• 单调性：$a_1\le a_2\le \cdots \le a_n$
• 锁定最大值：以 $a_i$
• 和约束：其余元素之和 $\le a_i$

2.3 01 背包 DP：统计方案数

现在问题变成了：给定若干个数，选出若干个数使其和

≤

S

\\leq S

≤S 的方案数。这正是 01 背包的计数版本。

定义

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 为前

i

i

i 个数中选出若干个数使其和恰好为

j

j

j 的方案数。状态转移：

d

p

[

i

]

[

j

]

=

d

p

[

i

−

1

]

[

j

]

+

d

p

[

i

−

1

]

[

j

−

a

i

]

dp[i][j] = dp[i-1][j] + dp[i-1][j-a_i]

dp[i][j]=dp[i−1][j]+dp[i−1][j−ai​]

其中：

• $dp[i-1][j]$
• $dp[i-1][j-a_i]$

初始化

d

p

[

0

]

[

0

]

=

1

dp[0][0] = 1

dp[0][0]=1（空集的和为

0

0

0，有

1

1

1 种方案）。

对于每个

i

i

i，以

a

i

a_i

ai​ 为最大值的非法子集数为：

∑

j

=

0

a

i

d

p

[

i

−

1

]

[

j

]

\\sum_{j=0}^{a_i} dp[i-1][j]

j=0∑ai​​dp[i−1][j]

这表示前

i

−

1

i-1

i−1 个数中选出和为

0

0

0 到

a

i

a_i

ai​ 的所有方案，每种方案加上

a

i

a_i

ai​ 后，总和

≤

2

a

i

\\leq 2a_i

≤2ai​，不满足多边形条件。

我们可以把 01 背包想象成天平称重：

• 你有若干砝码（木棍），每个只能用一次
• 你想知道能称出哪些重量（和）
• $dp[i][j]$
• 对于每个 $a_i$

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"非法子集计数器"：

整个过程就像海关查验：

• 所有货物（子集）先过一遍
• 挑出违禁品（非法子集）
• 剩下的就是合法货物（答案）

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 多边形方案数(木棍 a[1..n]):
mod = 998244353
ans = 2^n mod mod // 所有子集数
sort(a, 升序)

dp[0][0] = 1 // 空集
bad_ans = 0

for i = 1 to n:
for j = 0 to MAX_SUM:
dp[i][j] = dp[i-1][j]
if j >= a[i]:
dp[i][j] = (dp[i][j] + dp[i-1][j-a[i]]) mod mod

for j = 0 to a[i]:
bad_ans = (bad_ans + dp[i-1][j]) mod mod

return (ans – bad_ans – 1 + mod) mod mod

实战代码（一维优化通用模板）：

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5005;
const int mod = 998244353;

int n;
int a[N];
int dp[N];
int bad_ans;
int ans = 1;

signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ans = ans * 2 % mod;
}

sort(a + 1, a + n + 1);

dp[0] = 1;

for (int i = 1; i <= n; i++)
{
// 先统计以 a[i] 为最大值的非法子集
for (int j = 0; j <= a[i]; j++)
bad_ans = (bad_ans + dp[j]) % mod;

// 再更新 dp（逆序，01 背包）
for (int j = 5000; j >= a[i]; j—)
dp[j] = (dp[j] + dp[j – a[i]]) % mod;
}

cout << (ans – bad_ans – 1 + mod) % mod << endl;
return 0;
}

3.3 例题实现 —— 本题完整代码

#include <bits/stdc++.h>
using namespace std;

#define int long long // 使用长整型防止溢出
const int N = 5005; // 定义最大数组长度
const int mod = 998244353; // 模数

int n; // 数组元素个数
int a[N]; // 存储输入的数字数组
int dp[N][N]; // 动态规划数组，dp[i][j]表示前i个元素和为j的子集数
int bad_ans; // 统计不满足条件的子集数量
int ans = 1; // 总子集数（2^n），初始化为1

signed main()
{
// 输入数组长度
cin >> n;

// 输入数组元素并计算总子集数（2^n）
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ans *= 2; // 计算2的n次方
ans %= mod; // 取模防止溢出
}

// 对数组进行升序排序，保证从小到大排序
sort(a + 1, a + n + 1);

// 初始化动态规划数组：空集的和为0，有1种方式
dp[0][0] = 1;

// 动态规划：计算子集和分布
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 5000; j++) // 遍历所有可能的和（0到5000）
{
// dp[i][j]表示选到前i个数，所选数字的和为j的方案数
// 状态转移：不选a[i]
dp[i][j] = dp[i – 1][j];

// 选择当前元素a[i]（需要j>=a[i]）
if (j >= a[i])
{
dp[i][j] = (dp[i][j] + dp[i – 1][j – a[i]]) % mod;
}

// 统计不满足条件的子集：和j <= 当前元素a[i]
// 对于第i个数，它作为最大值的方案数是前i-1个数中
// 选出来的总和 <= a[i] 的方案数
if (j <= a[i])
{
bad_ans = (bad_ans + dp[i – 1][j]) % mod;
}
}
}

// 计算最终答案：总子集数 – 不满足条件的子集数 – 空集
// 公式：ans = 2^n – bad_ans – 1
cout << (ans – bad_ans – 1 + mod) % mod << endl;

return 0;
}

3.4 对比实现 —— 暴力枚举 vs 补集 DP

本题从 40 分到 100 分，经历了三个版本的优化：

对于本题，

n

≤

5000

n \\leq 5000

n≤5000 且

a

i

≤

5000

a_i \\leq 5000

ai​≤5000，所以

S

=

5000

S = 5000

S=5000 是可行的上界。01 背包的

O

(

n

⋅

S

)

=

O

(

2.5

×

10

7

)

O(n \\cdot S) = O(2.5 \\times 10^7)

O(n⋅S)=O(2.5×107) 完全在可接受范围内。

值得注意的是，本题的一维优化版本可以将空间复杂度从

O

(

n

⋅

S

)

O(n \\cdot S)

O(n⋅S) 降到

O

(

S

)

O(S)

O(S)，但二维版本更直观，适合理解。

3.5 变体清单 —— 常见变形

3.6 什么时候不能用？——边界条件和反例

补集转化虽然强大，但也有需要注意的边界：

• $n<3$
• 所有木棍相同：如 $a=[1,1,1,1]$
• 一根木棍极大：如 $a=[1,1,1,100]$
• 模数处理：减法取模时需要注意负数，(ans – bad_ans – 1 + mod) % mod 确保结果非负。
• 空集处理：$bad\_ans$

四、底层逻辑

4.1 为什么补集转化是正确的？

这是基于集合划分的基本原理。

设

U

U

U 为所有子集的集合（包括空集），

∣

U

∣

=

2

n

|U| = 2^n

∣U∣=2n。将

U

U

U 划分为三个互不相交的子集：

• $A$
• $B$
• $C$

则

U

=

A

∪

B

∪

C

U = A \\cup B \\cup C

U=A∪B∪C，且

A

,

B

,

C

A, B, C

A,B,C 两两不交。因此：

∣

A

∣

=

∣

U

∣

−

∣

B

∣

−

∣

C

∣

=

2

n

−

∣

B

∣

−

1

|A| = |U| – |B| – |C| = 2^n – |B| – 1

∣A∣=∣U∣−∣B∣−∣C∣=2n−∣B∣−1

我们的 DP 统计的就是

∣

B

∣

|B|

∣B∣（所有不满足条件的非空子集）。

为什么

B

B

B 可以这样统计？对于每个非空子集

S

∈

B

S \\in B

S∈B，设其最大元素为

a

i

a_i

ai​（排序后）。则

S

∖

{

a

i

}

S \\setminus \\{a_i\\}

S∖{ai​} 是从

{

a

1

,

…

,

a

i

−

1

}

\\{a_1, \\ldots, a_{i-1}\\}

{a1​,…,ai−1​} 中选出的一个子集，且其和

≤

a

i

\\leq a_i

≤ai​。反之，任何从

{

a

1

,

…

,

a

i

−

1

}

\\{a_1, \\ldots, a_{i-1}\\}

{a1​,…,ai−1​} 中选出的和

≤

a

i

\\leq a_i

≤ai​ 的子集，加上

a

i

a_i

ai​ 后都构成一个以

a

i

a_i

ai​ 为最大值的非法子集。

因此，

∣

B

∣

=

∑

i

=

1

n

∑

j

=

0

a

i

d

p

[

i

−

1

]

[

j

]

|B| = \\sum_{i=1}^n \\sum_{j=0}^{a_i} dp[i-1][j]

∣B∣=∑i=1n​∑j=0ai​​dp[i−1][j]，这正是我们的 DP 所计算的。

4.2 与经典问题的对比

这道题和经典的组合计数问题家族有密切联系：

可以看到，01 背包的计数版本是组合计数中最基础、最通用的工具之一。它的核心思想是：用 DP 数组记录"达到某个状态"的方案数，而非仅仅记录"是否可达"。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

• $a_i\le 5000$
• 严格大于：条件是 $\sum >2\max$
• 至少 $3$
• 下标集合不同即不同方案：这意味着即使长度相同但下标不同，也是不同方案。01 背包天然处理这一点（每个元素是独立的）。

五、决策表

面对"子集选择 + 约束判定 + 计数"类问题，如何快速选型？

一句话总结：子集计数想背包，约束复杂想补集，数量限制加维度，数据小则直接枚举。

六、工程视角

补集转化和 01 背包计数的思想在实际工程中有着广泛的应用：

七、小结

本文从一道 CSP-J 真题出发，探讨了补集转化与01 背包计数问题。

核心认知可以总结为：

当"满足条件"难以直接统计时，尝试统计"不满足条件"的方案数往往更简单；01 背包的计数版本是处理子集约束问题的通用武器，而排序后的单调性则是锁定问题结构的关键。

用公式化的语言概括：

答案

=

(

2

n

−

∑

i

=

1

n

∑

j

=

0

a

i

d

p

[

i

−

1

]

[

j

]

−

1

)

m

o

d

998244353

\\text{答案} = \\left(2^n – \\sum_{i=1}^n \\sum_{j=0}^{a_i} dp[i-1][j] – 1\\right) \\bmod 998244353

答案=(2n−i=1∑n​j=0∑ai​​dp[i−1][j]−1)mod998244353

其中

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 为前

i

i

i 个数中和为

j

j

j 的子集数，

d

p

[

i

]

[

j

]

=

d

p

[

i

−

1

]

[

j

]

+

d

p

[

i

−

1

]

[

j

−

a

i

]

dp[i][j] = dp[i-1][j] + dp[i-1][j-a_i]

dp[i][j]=dp[i−1][j]+dp[i−1][j−ai​]。

这道题教会我们的，不仅是如何写 01 背包和取模运算，更是一种**“正难则反”**的数学思维：在算法竞赛中，很多计数问题的正面攻击会遇到组合爆炸，但换个角度——统计反面——往往能找到多项式时间的解法。补集转化、容斥原理、对偶问题，都是这种"逆向思维"的具体体现。掌握这种思维方式，比记住任何具体算法都更重要。

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。