[CSP-J 2025] 多边形

GitHub 跳转原题关系图返回列表

排序后枚举最后一根被选木棍，用前缀子集和 DP 统计能与它组成多边形的方案数。

OJ: luogu

题目 ID: P14360

难度:普及/提高-

标签:cspjdp01背包枚举组合计数

日期: 2026-06-12 09:42

前置题目

luogu P2918[USACO08NOV] Buying Hay S把超过目标重量的状态统一截断到阈值，是本题只精确维护不超过值域上限的子集和、超过部分合并统计的直接前置思想。

题意

给定 n 根木棍，长度 a_i。求有多少种选木棍的方案（下标集合不同即不同），使得这些木棍能拼成一个多边形。

多边形条件：选 m 根木棍，长度之和大于最长木棍长度的两倍。

等价表述：除最长边外，其余边的和必须大于最长边。

思路

n 最大到 5000，直接枚举子集（ $2^n$ ）不可行。我们先保留最直接的暴力，用它看清题目要求的是“选哪些下标”：

先看一个可直接验证正确性的朴素枚举（仅适用于 n ≤ 20）：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long ans = 0;
    // 枚举所有子集 (2^n 种)
    for (int mask = 0; mask < (1 << n); mask++) {
        int m = __builtin_popcount(mask);
        if (m < 3) continue; // 至少需要 3 条边

        long long sum = 0, maxv = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                sum += a[i];
                maxv = max(maxv, (long long)a[i]);
            }
        }
        if (sum > 2 * maxv) ans++;
    }
    cout << ans % MOD << '\n';

    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按小木棍下标依次决定“选 / 不选”，递归生成完整选择后，叶子节点统一检查是否至少选 3 根且满足多边形条件：

另一种暴力写法：01 序列

cpp

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// brute_01_style.cpp：01 序列风格暴力，按小木棍下标依次决定选或不选。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MOD = 998244353;

int n;
int a[MAXN];
int choose_stick[MAXN]; // choose_stick[i] = 0/1，表示第 i 根木棍不选/选
long long answer;

bool check() {
    int chosen_count = 0;
    long long sum = 0;
    int max_len = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_stick[i] == 1) {
            chosen_count++;
            sum += a[i];
            max_len = max(max_len, a[i]);
        }
    }
    return chosen_count >= 3 && sum > 2LL * max_len;
}

void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) {
            answer++;
        }
        return;
    }

    // 第 dep 根木棍的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_stick[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    answer = 0;
    dfs(1);

    cout << answer % MOD << '\n';
    return 0;
}

brute.cpp 枚举所有子集并检验条件，复杂度 $O(2^n)$ ，只能通过测试点 1~6。

关键观察：枚举最后一根被选木棍

把所有木棍按长度从小到大排序。对于任意一个合法方案，在排序后的下标里，一定有一个最大的被选下标。

我们就枚举这个最大的被选下标 i。也就是说：

第 i 根木棍一定被选；
只能从前 i-1 根木棍中再选若干根；
因为数组已经排序，第 i 根木棍的长度 a[i] 就是这个方案的最大边。

多边形条件是：

\text{总和} > 2 \times \text{最大边}

如果前面选出的木棍总和为 s，当前最大边是 a[i]，条件变成：

s + a_i > 2a_i

也就是：

s > a_i

注意，题目还要求至少选 3 根木棍（m ≥ 3）。但条件 s > a_i 会自动保证这一点：前 i-1 根木棍每根长度都 ≤ a_i，要选出总和超过 a_i 的子集，至少需要选 2 根；再加上第 i 根，总共至少 3 根。因此只需维护 s > a_i 这一个不等式，无需额外判断 m。

所以第 i 根木棍对答案的贡献就是：

\text{前 } i-1 \text{ 根木棍中，子集和 } > a_i \text{ 的方案数}

这个做法不需要单独分类讨论“最大长度选了几根”。如果一个方案里选了多根同样的最大长度，它也只会在“这些最大长度木棍中下标最大的那一根”处被统计一次，因此不会重复计数。

DP 状态

设：

dp[s] = \text{已经处理过的前缀木棍中，选出若干根，总和恰好为 } s \text{ 的方案数}

在枚举第 i 根木棍时，dp 只包含前 i-1 根木棍。

由关键观察可知，我们需要统计前 i-1 根木棍中子集和 > a_i 的方案数。

最直接的思路是维护 dp 覆盖所有可能的子集和。前 i-1 根木棍总和上界为 $n · max_a = 5000 × 5000 = 2.5 × 10⁷$ ，空间无法承受；每轮转移 $O(n \cdot \max a)$ ，总复杂度 $O(n^2 \cdot \max a)$ ，不可行。

改用补集：令前 i-1 根木棍的全部子集数为

total = 2^{i-1}

则子集和 > a_i 的方案数等于

total - \sum_{s=0}^{a_i} dp[s]

其中 $\sum_{s=0}^{a_i} dp[s]$ 只需知道 dp[s] 在 $s \in [0, a_i]$ 的值。而题目保证 $a_i \leqslant 5000$ ，因此 dp 只需要精确维护 $[0, 5000]$ 这个范围。

至于子集和超过 5000 的情况：这些值必然大于任意 $a_i$ ，无需区分具体数值。在 0/1 背包转移时，s 从 $MAXV = 5000$ 倒序枚举到 a[i]，超过 5000 的和被主动丢弃，不写入 dp。这部分会通过 $total$ 减前缀和的方式被统一统计。

DP 状态转移

统计完第 i 根木棍的贡献后，再把第 i 根木棍加入前缀 DP，供后面的木棍使用。

第 i 根木棍只有“选 / 不选”两种可能，所以是一轮 0/1 背包转移：

dp_{new}[s] = dp_{old}[s] + dp_{old}[s-a_i]

实现时倒序枚举 s：

cpp

1
2
3for (int s = MAXV; s >= a[i]; s--) {
    dp[s] = dp[s] + dp[s - a[i]];
}

倒序的原因和标准 0/1 背包一样：每根木棍最多只能用一次。

样例 1 的 DP 状态转移表

下面这张表展示样例 1 1 2 3 4 5 中，枚举“最后一根被选木棍”时，dp 如何转移，以及答案如何累加。

当前下标 `i`	当前长度 `a[i]`	加入 `a[i]` 前的非零 `dp[s]`（只展示 $s <= 10$ ）	`sum_{s=0}^{a[i]} dp[s]`	前缀子集总数 $2^(i-1)$	本轮贡献	累计答案	加入 `a[i]` 后的非零 `dp[s]`（只展示 $s <= 10$ ）
1	1	`0:1`	1	1	0	0	`0:1, 1:1`
2	2	`0:1, 1:1`	2	2	0	0	`0:1, 1:1, 2:1, 3:1`
3	3	`0:1, 1:1, 2:1, 3:1`	4	4	0	0	`0:1, 1:1, 2:1, 3:2, 4:1, 5:1, 6:1`
4	4	`0:1, 1:1, 2:1, 3:2, 4:1, 5:1, 6:1`	6	8	2	2	`0:1, 1:1, 2:1, 3:2, 4:2, 5:2, 6:2, 7:2, 8:1, 9:1, 10:1`
5	5	`0:1, 1:1, 2:1, 3:2, 4:2, 5:2, 6:2, 7:2, 8:1, 9:1, 10:1`	9	16	7	9	`0:1, 1:1, 2:1, 3:2, 4:2, 5:3, 6:3, 7:3, 8:3, 9:3, 10:3`

表中的 s:x 表示当前 dp[s] = x。例如处理 i = 4, a[i] = 4 时，前面的小木棍是 1,2,3，前缀子集总数是 8，其中子集和 $<= 4$ 的有 6 个，所以子集和 > 4 的有 2 个，本轮贡献 2。处理 i = 5, a[i] = 5 时，前缀子集总数是 16 个，子集和 $<= 5$ 的有 9 个，因此子集和 > 5 的有 7 个，本轮贡献 7。最终累计答案为 $2 + 7 = 9$ ，正好对应样例 1 输出。

整个流程是：

排序。
预处理 pow2[i] = 2^i（模 MOD），初始化 dp[0] = 1。
从左到右枚举第 i 根木棍作为最后一根被选木棍。
用 pow2[i-1] - sum(dp[0..a[i]]) 统计本轮贡献。
再把 a[i] 加入前缀 0/1 背包。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXV = 5000;
const int MAXN = 5005;

int n;
int a[MAXN];
int dp[MAXV + 1];   // dp[s] 表示前缀木棍中选出若干根，总和恰好为 s 的方案数，只记录 s <= 5000
int pow2[MAXN];     // pow2[i] = 2^i

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);

    // 预处理 2 的幂：前 i 根木棍的全部子集数是 2^i。
    pow2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pow2[i] = 1LL * pow2[i - 1] * 2 % MOD;
    }

    dp[0] = 1; // 空集方案
    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        int x = a[i];

        // 枚举第 i 根作为“选中集合中下标最大的木棍”。
        // 前 i-1 根的全部子集数。
        int total = pow2[i - 1];

        // 前 i-1 根中，子集和 <= x 的方案数。
        int leq = 0;
        for (int s = 0; s <= x; s++) {
            leq += dp[s];
            if (leq >= MOD) leq -= MOD;
        }

        // 若前面选出的木棍总和 > x，则加上当前木棍 x 后满足 sum > 2 * x。
        int greater = (total - leq + MOD) % MOD;
        ans += greater;
        ans %= MOD;

        // 把第 i 根木棍加入前缀 0/1 背包。
        // 超过 5000 的和不再细分，后续用 total - 前缀和统一统计。
        for (int s = MAXV; s >= x; s--) {
            dp[s] += dp[s - x];
            if (dp[s] >= MOD) dp[s] -= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n \times V)$ ，其中 $V = 5000$ ，约 $2.5 \times 10^7$ 次运算
空间复杂度： $O(V)$

总结

本题更自然的切入点是“每个方案只在最后一根被选木棍处统计一次”。排序以后，枚举这个最后下标，就把多边形条件转成了“前缀子集和是否大于当前长度”。再利用长度上限 5000，只精确维护不超过 5000 的子集和，超过部分用总方案数减去前缀和统一统计。

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

text

1
25
1 2 3 4 5

输出 #1

text

输入输出样例 #2

输入 #2

text

1
25
2 2 3 8 10

输出 #2

text

说明/提示

【样例 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$ 。

::cute-table{tuack}

测试点编号	$n \leq$	$\max_{i=1}^{n} a_i \leq$
$1 \sim 3$	$3$	$10$
$4 \sim 6$	$10$	$10^2$
$7 \sim 10$	$20$	^
$11 \sim 14$	$500$	^
$15 \sim 17$	^	$1$
$18 \sim 20$	$5\,000$	^
$21 \sim 25$	^	$5\,000$