[CSP-J 2025] 多边形 题解

题目分析

本题要求从 $n$ 根小木棍（长度分别为 $a_1, \dots, a_n$）中选择至少 3 根，使得拼成多边形。 多边形拼合条件：

求选出小木棍的合法方案数对 $998,244,353$ 取模的结果。

核心转化

1. 确定最长边： 将所有木棍升序排序：$a_1 \leq a_2 \leq \dots \leq a_n$。 我们枚举选出的木棍集合中下标最大（最长）的木棍为第 $i$ 根（长度为 $a_i$）。 则集合中其余被选中的木棍必定来自下标 $\{1, 2, \dots, i-1\}$。

2. 化简多边形条件： 设其余选中的木棍长度之和为 $S_{rest}$。 根据条件：

   $$S_{rest} + a_i > 2 a_i \iff S_{rest} > a_i$$

   注意：

   • 因为每个木棍长度 $a_j \geq 1$，若 $S_{rest} > a_i$，由于集合内其他任何单根木棍的长度都 $\leq a_i$，所以必然至少选择了 2 根其他木棍；
   • 加上第 $i$ 根木棍本身，选出的木棍总数至少为 $1 + 2 = 3$ 根，自动满足 $m \geq 3$ 的条件！

3. 正难则反（背包 DP）： 对于第 $i$ 根木棍，在前面的 $i-1$ 根木棍中，共有 $2^{i-1}$ 种不同的选取子集。 其中不合法的方案数，就是其余木棍长度和 $S_{rest} \leq a_i$ 的方案数。 因此：

   $$\text{以 } a_i \text{ 为最大边的合法方案数} = 2^{i-1} - \sum_{S=0}^{a_i} (\text{前 } i-1 \text{ 根木棍中和为 } S \text{ 的方案数})$$

动态规划设计

• 题目保证 $\max a_i \leq 5000$。
• 定义状态 $dp[s]$ 表示当前已经处理过的元素中，子集和为 $s$ 的方案数。
• 初始状态：$dp[0] = 1$，其余 $dp[s] = 0$。
• 遍历 $i$ 从 $1$ 到 $n$：
  1. 计算 $\text{invalid} = \sum_{s=0}^{a_i} dp[s] \pmod{998244353}$；
  2. $\text{ans} = (\text{ans} + 2^{i-1} - \text{invalid}) \pmod{998244353}$；
  3. 将当前木棍 $a_i$ 加入背包： 倒序更新 $s$ 从 $5000$ 到 $a_i$：$$dp[s] = (dp[s] + dp[s - a_i]) \bmod 998244353$$
• 遍历结束后，$\text{ans}$ 即为最终答案。

复杂度分析

• 时间复杂度：$O(n \log n + n \times \max(a_i))$。 对于 $n \leq 5000, \max(a_i) \leq 5000$，$5000 \times 5000 = 2.5 \times 10^7$ 次运算，在 C++ 中耗时在 0.1 秒左右，轻松通过。
• 空间复杂度：$O(\max(a_i)) = O(5000)$，仅占用微量内存。

参考代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;
const int MAX_A = 5000;

int dp[MAX_A + 1];

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

    int n;
    if (!(cin >> n)) return 0;

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

    sort(a.begin(), a.end());

    dp[0] = 1;
    long long ans = 0;
    long long pow2 = 1;

    for (int i = 0; i < n; ++i) {
        int val = a[i];

        long long invalid = 0;
        for (int s = 0; s <= val && s <= MAX_A; ++s) {
            invalid = (invalid + dp[s]) % MOD;
        }

        ans = (ans + pow2 - invalid + MOD) % MOD;

        for (int s = MAX_A; s >= val; --s) {
            dp[s] = (dp[s] + dp[s - val]) % MOD;
        }

        pow2 = (pow2 * 2) % MOD;
    }

    cout << ans << "\n";

    return 0;
}

参考代码 (Python 3)

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    a = [int(x) for x in input_data[1:n+1]]

    MOD = 998244353
    a.sort()
    max_a = 5000

    dp = [0] * (max_a + 1)
    dp[0] = 1
    ans = 0
    pow2 = 1

    for i in range(n):
        val = a[i]
        invalid = sum(dp[:min(val + 1, max_a + 1)]) % MOD
        ans = (ans + pow2 - invalid) % MOD

        for s in range(max_a, val - 1, -1):
            dp[s] = (dp[s] + dp[s - val]) % MOD

        pow2 = (pow2 * 2) % MOD

    print(ans)

if __name__ == "__main__":
    main()