【CSP】CSP-J 2025真题 | 多边形 luogu-P14360 （相当于GESP六级水平）
CSP-J 2025真题- 多边形，动态规划考点，适合GESP六级及以上水平的考生练习，难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
P14360 [CSP-J 2025] 多边形
题目要求
题目描述
小 R 喜欢玩小木棍。小 R 有 $n$ 根小木棍，第 $i$ ($1 \leq i \leq n$) 根小木棍的长度为 $a_i$。
小 X 希望小 R 从这 $n$ 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 $l_1, l_2, \dots, l_m$ 的 $m$ 根小木棍，这 $m$ 根小木棍能拼成一个多边形当且仅当 $m \geq 3$ 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 $\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i$。
由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 $1 \leq i \leq n$，使得其中一种方案选择了第 $i$ 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。
输入格式
输入的第一行包含一个正整数 $n$，表示小 R 的小木棍的数量。
输入的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示小 R 的小木棍的长度。
输出格式
输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 $998,244,353$ 取模后的结果。
输入输出样例 #1
输入 #1
1
2
5
1 2 3 4 5
输出 #1
1
9
输入输出样例 #2
输入 #2
1
2
5
2 2 3 8 10
输出 #2
1
6
说明/提示
【样例 1 解释】
共有以下 $9$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
- 选择第 $2, 3, 4$ 根小木棍，长度之和为 $2 + 3 + 4 = 9$，长度最大值为 $4$;
- 选择第 $2, 4, 5$ 根小木棍，长度之和为 $2 + 4 + 5 = 11$，长度最大值为 $5$;
- 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 4 + 5 = 12$，长度最大值为 $5$;
- 选择第 $1, 2, 3, 4$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 = 10$，长度最大值为 $4$;
- 选择第 $1, 2, 3, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 5 = 11$，长度最大值为 $5$;
- 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 4 + 5 = 12$，长度最大值为 $5$;
- 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $1 + 3 + 4 + 5 = 13$，长度最大值为 $5$;
- 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 4 + 5 = 14$，长度最大值为 $5$;
- 选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 + 5 = 15$，长度最大值为 $5$。
【样例 2 解释】
共有以下 $6$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
- 选择第 $1, 2, 3$ 根小木棍，长度之和为 $2 + 2 + 3 = 7$，长度最大值为 $3$;
- 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 8 + 10 = 21$，长度最大值为 $10$;
- 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 8 + 10 = 22$，长度最大值为 $10$;
- 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
- 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
- 选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 3 + 8 + 10 = 25$，长度最大值为 $10$。
【样例 3】
见选手目录下的 $\textit{\textbf{polygon/polygon3.in}}$ 与 $\textit{\textbf{polygon/polygon3.ans}}$。
该样例满足测试点 $7 \sim 10$ 的约束条件。
【样例 4】
见选手目录下的 $\textit{\textbf{polygon/polygon4.in}}$ 与 $\textit{\textbf{polygon/polygon4.ans}}$。
该样例满足测试点 $11 \sim 14$ 的约束条件。
【子任务】
对于所有测试数据，保证：
- $3 \leq n \leq 5\,000$;
- 对于所有 $1 \leq i \leq n$，均有 $1 \leq a_i \leq 5\,000$。
| 测试点编号 | $n \leq$ | $\max_{i=1}^{n} a_i \leq$ |
|---|---|---|
| $1 \sim 3$ | $3$ | $10$ |
| $4 \sim 6$ | $10$ | $10^2$ |
| $7 \sim 10$ | $20$ | $10^2$ |
| $11 \sim 14$ | $500$ | $10^2$ |
| $15 \sim 17$ | $500$ | $1$ |
| $18 \sim 20$ | $5\,000$ | $1$ |
| $21 \sim 25$ | $5\,000$ | $5\,000$ |
题目分析
本题考查 动态规划 (Dynamic Programming) 和 背包问题 (Knapsack Problem) 的变体，结合了 多边形构成条件 的几何性质。
1. 问题转化
首先，我们需要理解多边形的构成条件：$m$ 根木棍能拼成多边形，当且仅当 $m \ge 3$ 且所有木棍长度之和 > 最长木棍长度的 2 倍。 即：$\sum l_i > 2 \times \max(l_i)$。 如果我们把最长的木棍单独拿出来，剩下的木棍长度之和设为 $S_{others}$，最长木棍长度为 $L_{max}$，那么总和 $\sum l_i = S_{others} + L_{max}$。 条件不等式变为：$S_{others} + L_{max} > 2 \times L_{max} \implies S_{others} > L_{max}$。
也就是说，只要我们选定了一根最长的木棍（长度为 $L$），剩下的木棍长度之和必须严格大于 $L$。
2. 解题思路
如果我们枚举哪一根木棍作为“最长木棍”，问题就会变得简单很多。 为了方便枚举确定“最长木棍”，我们可以先将所有木棍按长度从小到大排序。 设排序后的木棍长度为 $a_1, a_2, \dots, a_n$。
当我们考虑第 $i$ 根木棍 $a_i$ 作为选出的集合中的最大值时：
- 这意味着我们只从下标小于 $i$ 的木棍中做选择（因为它们更短，或者虽然长度相同但我们按排序顺序处理，避免重复计算）。
- 我们需要从前 $i-1$ 根木棍中选出若干根，使得它们的长度之和 $S > a_i$。
- 一旦满足 $S > a_i$，加上 $a_i$ 本身，我们就有了至少 2 根木棍（如果 $S > 0$），且满足多边形条件。
- 疑问：$m \ge 3$ 的条件怎么办？
- 分析：如果只选了 1 根其他木棍 $a_j$ ($j < i$)，那么 $S = a_j$。我们需要 $a_j > a_i$。但已排序保证 $a_j \le a_i$，矛盾。所以 $S > a_i$ 必然隐含了至少需要 2 根其他木棍。所以只要满足 $S > a_i$，就自动满足 $m \ge 3$。
3. 动态规划 (DP) 设计逻辑与思想
本题的核心难点在于如何高效统计满足 $S > a_i$ 的方案数。直接搜索或暴力枚举复杂度过高，因此我们需要借助动态规划 (DP) 来通过“组合”的方式计算和的分布。
3.1 核心思想：补集转化 (Complement Strategy)
对于固定的最大边 $a_i$，我们需要满足的条件是： \(\sum_{selected} side > a_i\) 由于 $a_i$ 最大只有 $5000$，而 $n$ 可以达到 $5000$，选出的边的总和可能非常大（最大可达 $2.5 \times 10^7$）。如果我们定义 DP 状态来记录“和为 $S$”的方案数，直接记录所有可能的 $S$ 会导致空间爆炸，且计算量过大。
观察发现，不合法的条件是： \(\sum_{selected} side \le a_i\) 此时的和 $S$ 的范围被限制在了 $[0, 5000]$ 之间。这个范围非常小！ 因此，我们的策略是：
- 计算前 $i-1$ 个元素的所有子集总数（即 $2^{i-1}$）。
- 计算不合法的方案数（即子集和 $\le a_i$ 的方案数）。
- 合法方案数 = 总方案数 - 不合法方案数。
3.2 状态定义 (State Definition)
基于上述分析，我们只需要关心“和为 $j$”的方案数，其中 $0 \le j \le 5000$。 定义状态 $dp[j]$：
$dp[j]$ 表示在当前已经考虑过的木棍集合中，选出若干根木棍，使其长度之和恰好为 $j$ 的方案数。
- 初始状态：$dp[0] = 1$。
- 含义：从空集中选出和为 0 的方案只有 1 种（即什么都不选）。
- 其他 $dp[j] = 0$。
3.3 状态转移 (State Transition)
随着我们按顺序遍历排序后的木棍 $a_1, a_2, \dots, a_n$，每处理完一个 $a_i$（即把它作为最大边的可能性计算完后），我们就需要将 $a_i$ 放入我们的“可选池”中，供后续更大的边作为“以前的木棍”使用。 这时候，问题就变成了一个0/1 背包计数问题：
- 对于一个新的物品（长度为 $x = a_i$），我们要更新所有可能的和 $j$。
- 想要凑出和 $j$，有两种选择：
- 不选这个新物品 $x$：方案数即为之前的 $dp[j]$。
- 选这个新物品 $x$：此前必须已经凑出了 $j - x$，方案数为之前的 $dp[j - x]$。
因此，转移方程为： \(dp_{new}[j] = dp_{old}[j] + dp_{old}[j - x]\)
3.4 二维数组实现（基础版）
在理解一维数组优化之前，我们先来看看如果不进行空间优化，标准的二维动态规划长什么样。
- 状态定义：$dp[i][j]$ 表示在考虑前 $i$ 根木棍时，从中选出若干根，使其长度之和恰好为 $j$ 的方案数。
- 状态转移： 当我们处理第 $i$ 根木棍（长度为 $x = a_i$）时，对于任意的和 $j$，我们有两种选择：
- 不选这根木棍：方案数继承自处理前 $i-1$ 根木棍时的结果，即 $dp[i-1][j]$。
- 选这根木棍：前提是前 $i-1$ 根木棍能凑出 $j-x$，方案数为 $dp[i-1][j-x]$。
所以，转移方程为： \(dp[i][j] = dp[i-1][j] + dp[i-1][j-x]\)
在这个二维表格中，计算第 $i$ 行的值时，完全依赖于第 $i-1$ 行的值，这为空间优化提供了基础。
3.5 空间优化：从二维到一维（进阶版）
为了节省空间，我们可以把二维数组压缩成一维数组。 观察上面的公式，$dp[i][j]$ 只和上一行的 $dp[i-1][…]$ 有关。那我们能不能直接用一个数组 dp[j] 来同时存储“上一行”和“当前行”的数据呢？
答案是可以的，但要注意更新顺序。
当我们计算 dp[j]（即 $dp[i][j]$）时，我们需要用到 dp[j-x]。
- 这个
dp[j-x]必须代表的是 $dp[i-1][j-x]$（上一行的数据，也就是还没有考虑当前木棍 $x$ 时的旧数据）。
如果我们在更新 dp 数组时，从大到小遍历 $j$：
- 计算
dp[j]时，我们需要读取dp[j-x]。 - 因为 $j-x < j$，而我们是从大到小遍历，所以
dp[j-x]此时还没有被更新过。 - 因此，它保留的正是上一轮（$i-1$）的值。这正是我们想要的！
反之，如果我们从小到大遍历 $j$：
- 当计算到
dp[j]时，dp[j-x]（下标比 $j$ 小）已经被更新过了。 - 此时
dp[j-x]里面存放的已经是 $dp[i][j-x]$（这一轮的新值，已经选过 $x$ 了）。 - 再把它加到
dp[j]里，就相当于 $x$ 被选了两次。这变成了“完全背包”问题，不符合题目“每根木棍只能用一次”的要求。
举例说明： 假设当前 $dp$ 数组只有 $dp[0]=1$（其余为0），现在新来了一根长度 $x=2$ 的木棍。
- 错误做法（从小到大）：
- $j=2$：$dp[2] = dp[2] + dp[0] = 0 + 1 = 1$。（此时 $dp[2]$ 变成了 1，表示选了 $x$）
- $j=4$：$dp[4] = dp[4] + dp[2]$。注意！此时读到的 $dp[2]$ 已经是 1 了。
- $dp[4] = 0 + 1 = 1$。这意味着我们可以凑出 4，相当于选了两个 $x$（$2+2$）。这与“每根木棍只有一根”矛盾。
- 正确做法（从大到小）：
- $j=4$：$dp[4] = dp[4] + dp[2] = 0 + 0 = 0$。（此时 $dp[2]$ 还是旧值 0）
- $j=2$：$dp[2] = dp[2] + dp[0] = 0 + 1 = 1$。
- 最终结果：$dp[2]=1, dp[4]=0$。正确。
4. 算法流程
- 排序：将数组 $a$ 从小到大排序。
- 初始化：$dp[0] = 1$（空集和为 0），其余为 0。记录
total_subsets= 1（初始只有空集）。 - 遍历：对于每根木棍 $a_i$ ($1 \le i \le n$)：
- 统计贡献：
- 当前最大边是 $a_i$。
- 不合法的情况总数
invalid= $\sum_{k=0}^{a_i} dp[k]$。（即前 $i-1$ 个元素中和 $\le a_i$ 的方案数） - 合法方案数 =
total_subsets-invalid。（注：total_subsets即为前 $i-1$ 个元素的所有子集总数 $2^{i-1}$） - 累加到最终答案
ans中。
- 更新 DP： 在处理完 $a_i$ 的贡献（即统计完以 $a_i$ 为最大边的情况）后，我们需要把 $a_i$ 加入到“已处理集合”中，以便后续更大的边使用。 这本质上是一个 0/1 背包问题 的计数模型。
- 状态定义：$dp[j]$ 表示使用之前所有已处理的木棍，能凑出和为 $j$ 的方案数。
- 状态转移：对于当前的新木棍 $a_i$，凑出和为 $j$ 有两种方式：
- 不选 $a_i$：方案数等于处理 $a_i$ 之前的 $dp[j]$。
- 选 $a_i$：需要先凑出 $j - a_i$ 的和，然后加上 $a_i$。方案数等于处理 $a_i$ 之前的 $dp[j - a_i]$。
- 因此，更新后的状态为：$dp_{new}[j] = dp_{old}[j] + dp_{old}[j - a_i]$。
- 倒序枚举：为了在原地数组上更新且保证 $a_i$ 只被使用一次（0/1 背包特性），我们需要从大到小枚举 $j$（从 5000 到 $a_i$）。
- 如果从小到大枚举，计算 $dp[j]$ 时引用的 $dp[j - a_i]$ 可能是已经加入过 $a_i$ 的新值，这会导致 $a_i$ 被重复选取（变成完全背包）。
- 倒序枚举保证了计算 $dp[j]$ 时，$dp[j - a_i]$ 还是上一轮（未加入 $a_i$）的状态。
- 更新总方案数：
total_subsets变为原来的 2 倍。因为对于之前存在的每一个子集，我们都可以选择“加入 $a_i$”或“不加入 $a_i$”，从而裂变成两个新的子集。
- 统计贡献：
5. 复杂度分析
- 时间复杂度：外层循环 $n$ 次，内层 DP 更新和求和常数 $C = 5000$。总复杂度 $O(n \cdot \max(a_i))$。代入数据 $5000 \times 5000 = 2.5 \times 10^7$，在 1 秒时限内可以通过。
- 空间复杂度：$O(\max(a_i))$，只需一个大小为 5005 的数组。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <algorithm>
#include <iostream>
#include <vector>
const int MOD = 998244353;
const int MAX_VAL = 5005; // a_i 最大值是 5000
int dp[MAX_VAL]; // dp[s] 表示当前已处理的小木棍中，和为 s 的子集数量
int main() {
// 优化 I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
// 1. 排序：从小到大处理，保证处理 a[i] 时，它就是当前子集的最大值
std::sort(a.begin(), a.end());
// 初始化 DP
// dp[0] = 1 (空集和为0)
for (int i = 0; i < MAX_VAL; ++i) dp[i] = 0;
dp[0] = 1;
long long ans = 0;
long long total_subsets = 1; // 2^i, 初始也就是 2^0 = 1 (对应处理第一个元素之前)
for (int i = 0; i < n; ++i) {
int limit = a[i];
// 2. 统计 “不合法” 的方案数
// 所谓不合法，就是“除去最大边 a[i] 后，其余边之和 <= a[i]”。
// 我们之前维护的 dp[s] 就是 sum=s 的方案数。
// 所以我们把 s 从 0 到 a[i] 的所有 dp[s] 累加起来。
long long invalid_count = 0;
// 细节：循环上界取 limit (也就是 a[i])。
// 虽然 dp 数组最大只有 5005，但 a[i] 最大也就 5000，不会越界。
// 一般为了严谨会写 min(limit, MAX_VAL - 1)，但本题数据范围保证 limit < MAX_VAL。
for (int s = 0; s <= limit; ++s) {
// 累加所有满足 "其他边之和 s <= 最大边 a[i]" 的情况
// 这些情况都无法与 a[i] 组成多边形
invalid_count = (invalid_count + dp[s]) % MOD;
}
// 3. 计算以 a[i] 为最大边的贡献 (核心 MOD 运算逻辑)
// 公式：贡献 = 总子集数 - 不合法数
// C++ 中取模的坑：(A - B) % P 可能会变成负数！
// 比如 (2 - 5) % 10 = -3，但我们需要的是正余数 7。
// 解决方法：((A - B) % P + P) % P，或者简化为 (A - B + P) % P。
long long contribution = (total_subsets - invalid_count + MOD) % MOD;
// 根据模运算性质，每一步加减乘结果取模，最终结果依然正确
ans = (ans + contribution) % MOD;
// 4. 更新 DP 数组，加入 a[i]
// 核心逻辑：类似于 0/1 背包，必须**从大到小**更新
// 为什么？因为 dp[j] = dp[j] + dp[j - limit]
// 我们希望右边的 dp[j - limit] 是**上一轮**（还没加入 a[i] 时）的值。
// 如果从小到大更新，dp[j - limit] 可能已经被更新过（包含了 a[i]），
// 导致 a[i] 被重复使用（相当于完全背包），这违反了“每根木棍只能用一次”的规则。
// 更新范围：从 MAX_VAL - 1 到 a[i]
for (int j = MAX_VAL - 1; j >= limit; --j) {
// 加法取模：(A + B) % P，防止溢出。
dp[j] = (dp[j] + dp[j - limit]) % MOD;
}
// 更新总子集数 * 2
// 逻辑：对于之前存在的每一个子集，现在都有“选 a[i]”和“不选 a[i]”两种情况
// 所以子集总数翻倍。total_subsets 维护的是 2^i
total_subsets = (total_subsets * 2) % MOD;
}
std::cout << ans << std::endl;
return 0;
}
💡 关键细节：为什么要每一步都取模？
很多同学会有疑问：为什么不能把所有结果算出来，最后再取模？
- 防止溢出：本题中最大可能有 $2^{5000}$ 种方案，这是一个天文数字，
long long也远远存不下（long long大约只能存 $2^{63}$）。如果不每一步都取模，计算结果瞬间就会由正变负（溢出），导致错误。- 取模的性质：模运算满足加法、减法和乘法的结合律。
- $(A + B) \pmod P = ((A \pmod P) + (B \pmod P)) \pmod P$
- $(A \times B) \pmod P = ((A \pmod P) \times (B \pmod P)) \pmod P$ 这保证了 “每一步取模” 算出来的结果，和 “最后再取模” 的结果是完全一样的。
- 注意：减法比较特殊，$(A - B) \pmod P$ 可能会得到负数，所以在 C++ 中需要写成
(A - B + P) % P来保证结果为正。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
