2025真题 | 多边形 luogu-P14360

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

5
1 2 3 4 5

输出 #1

输入输出样例 #2

输入 #2

5
2 2 3 8 10

输出 #2

说明/提示

【样例 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$ $S > a_{i}$ ，加上 $a_i$ $a_{i}$ 本身，我们就有了至少 2 根木棍（如果 $S > 0$ $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$ $d p [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$ $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. 算法流程

排序：将数组 $a$ 从小到大排序。
初始化： $dp[0] = 1$ （空集和为 0），其余为 0。记录 total_subsets = 1（初始只有空集）。
遍历：对于每根木棍 $a_i$ $a_{i}$ ( $1 \le i \le n$ $1 \leq i \leq 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$ $a_{i}$ 为最大边的情况）后，我们需要把 $a_i$ $a_{i}$ 加入到“已处理集合”中，以便后续更大的边使用。这本质上是一个 0/1 背包问题 的计数模型。
  - 状态定义： $dp[j]$ 表示使用之前所有已处理的木棍，能凑出和为 $j$ 的方案数。
  - 状态转移：对于当前的新木棍 $a_i$ $a_{i}$ ，凑出和为 $j$ $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$ $a_{i}$ 只被使用一次（0/1 背包特性），我们需要从大到小枚举 $j$ $j$ （从 5000 到 $a_i$ $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 的数组。

示例代码

#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 来保证结果为正。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月24日

2025真题 | 异或和 luogu-P14359 2024真题 | 扑克牌 luogu-P11227