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$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

1. 选择第 $2, 3, 4$ 根小木棍，长度之和为 $2 + 3 + 4 = 9$，长度最大值为 $4$;
2. 选择第 $2, 4, 5$ 根小木棍，长度之和为 $2 + 4 + 5 = 11$，长度最大值为 $5$;
3. 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 4 + 5 = 12$，长度最大值为 $5$;
4. 选择第 $1, 2, 3, 4$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 = 10$，长度最大值为 $4$;
5. 选择第 $1, 2, 3, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 5 = 11$，长度最大值为 $5$;
6. 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 4 + 5 = 12$，长度最大值为 $5$;
7. 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $1 + 3 + 4 + 5 = 13$，长度最大值为 $5$;
8. 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 4 + 5 = 14$，长度最大值为 $5$;
9. 选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 + 5 = 15$，长度最大值为 $5$。

【样例 2 解释】

共有以下 $6$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

1. 选择第 $1, 2, 3$ 根小木棍，长度之和为 $2 + 2 + 3 = 7$，长度最大值为 $3$;
2. 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 8 + 10 = 21$，长度最大值为 $10$;
3. 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 8 + 10 = 22$，长度最大值为 $10$;
4. 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
5. 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
6. 选择第 $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$。

题目分析

本题考查 动态规划 (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$ 作为选出的集合中的最大值时：

1. 这意味着我们只从下标小于 $i$ 的木棍中做选择（因为它们更短，或者虽然长度相同但我们按排序顺序处理，避免重复计算）。
2. 我们需要从前 $i-1$ 根木棍中选出若干根，使得它们的长度之和 $S > a_i$。
3. 一旦满足 $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]$ 之间。这个范围非常小！ 因此，我们的策略是：

1. 计算前 $i-1$ 个元素的所有子集总数（即 $2^{i-1}$）。
2. 计算不合法的方案数（即子集和 $\le a_i$ 的方案数）。
3. 合法方案数 = 总方案数 - 不合法方案数。

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$，有两种选择：
  1. 不选这个新物品 $x$：方案数即为之前的 $dp[j]$。
  2. 选这个新物品 $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$，我们有两种选择：
  1. 不选这根木棍：方案数继承自处理前 $i-1$ 根木棍时的结果，即 $dp[i-1][j]$。
  2. 选这根木棍：前提是前 $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. 算法流程

1. 排序：将数组 $a$ 从小到大排序。
2. 初始化：$dp[0] = 1$（空集和为 0），其余为 0。记录 total_subsets = 1（初始只有空集）。
3. 遍历：对于每根木棍 $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$ 有两种方式：
       1. 不选 $a_i$：方案数等于处理 $a_i$ 之前的 $dp[j]$。
       2. 选 $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;
}

💡 关键细节：为什么要每一步都取模？

很多同学会有疑问：为什么不能把所有结果算出来，最后再取模？

1. 防止溢出：本题中最大可能有 $2^{5000}$ 种方案，这是一个天文数字，long long 也远远存不下（long long 大约只能存 $2^{63}$）。如果不每一步都取模，计算结果瞬间就会由正变负（溢出），导致错误。
2. 取模的性质：模运算满足加法、减法和乘法的结合律。
   • $(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)，考试认证学员交流，互帮互助