题解：P14360 [CSP-J 2025] 多边形 / polygon（民间数据）

RootSign · 2025-11-01 19:06:32 · 题解

P14360 [CSP-J 2025] 多边形 / polygon 题解

题目分析

给定 n 根长度为 a_i 的木棍，求有多少种选择方案使得选出的木棍能拼成多边形。

多边形条件：至少选 3 根木棍，且满足 \sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i。

答案对 998244353 取模。

数据范围分析

根据题目给出的测试点分布进行数据分层：

算法一：组合数学（特殊性质：全为 1）

适用范围： a_i = 1 对所有 i 成立

时间复杂度： O(n)

核心思想： 当所有木棍长度都是 1 时，选 k 根木棍，最大值必为 1，条件变为：

即只要选择 \geq 3 根木棍即可。

答案公式：

推导：

• 总方案数：2^n
• 减去选 0 根：1
• 减去选 1 根：n
• 减去选 2 根：\binom{n}{2}

代码实现：

long long qpow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

long long C(int n, int m) {
    if (m > n || m < 0) return 0;
    long long num = 1, den = 1;
    for (int i = 0; i < m; i++) {
        num = num * (n - i) % MOD;
        den = den * (i + 1) % MOD;
    }
    return num * qpow(den, MOD - 2) % MOD;
}

// 特殊性质判断
bool allOne = true;
for (int i = 1; i <= n; i++) {
    if (a[i] != 1) {
        allOne = false;
        break;
    }
}

if (allOne) {
    long long ans = qpow(2, n);
    ans = (ans - 1 - n - C(n, 2) % MOD + 2LL * MOD) % MOD;
    cout << ans << endl;
    return;
}

算法二：暴力枚举 (pts 1-10)

适用范围： n \leq 20

时间复杂度： O(2^n \times n)

核心思想： 直接 DFS 枚举所有子集，对每个子集判断是否满足条件。

对于每个位置可以选或不选，最终检查：

1. 选出的木棍数量 \geq 3
2. \sum l_i > 2 \times \max l_i

代码实现：

if (n <= 20) {
    long long ans = 0;

    function<void(int, int, int, int)> dfs = [&](int pos, int cnt, int sum, int maxval) {
        if (pos == n + 1) {
            if (cnt >= 3 && sum > 2 * maxval) {
                ans++;
                ans %= MOD;
            }
            return;
        }
        dfs(pos + 1, cnt, sum, maxval);
        dfs(pos + 1, cnt + 1, sum + a[pos], max(maxval, a[pos]));
    };

    dfs(1, 0, 0, 0);
    cout << ans << endl;
}

算法三：容斥优化 (pts 11-14, 21-25)

适用范围： n > 20 且非全 1

时间复杂度： O(n \times V)，其中 V = \max(a_i)

核心思想： 对于第 i 根作为最大值，从前 i-1 根任意选的方案数为 2^{i-1}，减去不合法方案数。

关键思路

枚举每根木棍作为最大值 M，需要满足：

• 从前面的木棍中选若干根
• 选出的木棍总和 S 满足 S + M > 2M，即 S > M
• 至少选 2 根其他木棍（加上最大值共 3 根）

容斥原理：

• 从前 i-1 根任意选：2^{i-1} 种方案
• 不合法方案：选出的和 \leq M

则答案为：

算法步骤

1. 排序数组：方便枚举最大值
2. 背包 DP：用 f[j] 表示从前若干根木棍中选出和为 j 的方案数
3. 边插入边统计：
   • 处理第 i 根木棍时，更新 f 数组
   • 计算 sum[i]：第 i 个位置不合法方案数（和 \leq a[i+1]）
4. 累加答案：对于每个位置 i \geq 3，答案加上 2^{i-1} - sum[i-1]

关键优化

为什么 sum[i] 统计的是和 \leq a[i+1]？

因为处理第 i 根时，f 数组包含了前 i 根的所有组合。当第 i+1 根作为最大值时，不合法方案就是从前 i 根中选出和 \leq a[i+1] 的方案。

初始化：

状态转移：

对于第 i 根木棍：

1. 更新背包：f[j] \gets f[j] + f[j - a[i]]（从后往前）
2. 统计不合法方案：sum[i] = \sum_{j=0}^{a[i+1]} f[j]

快速幂计算 2^k：

使用递归 + 位运算优化，左移一位相当于乘 2。

int qpow2(int b) {
    if (!b) return 1;
    int res = qpow2(b >> 1);
    res = (1ll * res * res) % MOD;
    if (b & 1) (res <<= 1) %= MOD;
    return res;
}

完整代码实现

else {
    int f[MAXV], sum[MAXN];
    memset(f, 0, sizeof(f));
    memset(sum, 0, sizeof(sum));

    sort(a + 1, a + n + 1);

    f[a[1]] = f[0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = MAXV - 1; j >= a[i]; j--) {
            (f[j] += f[j - a[i]]) %= MOD;
        }
        for (int j = 0; j <= a[i + 1]; j++) {
            (sum[i] += f[j]) %= MOD;
        }
    }

    int ans = 0;
    for (int i = 3; i <= n; i++) {
        (ans += (qpow2(i - 1) - sum[i - 1] + MOD) % MOD) %= MOD;
    }

    cout << ans << endl;
}

复杂度总结

其中 V = \max(a_i) \leq 5000。

核心技巧总结

1. 特殊性质优化：利用 a_i = 1 的性质简化为组合数问题
2. 枚举最大值：将问题转化为从剩余木棍中选择的方案数统计
3. 容斥原理：总方案数 - 不合法方案数
4. 背包 DP：统计选出特定和的方案数
5. 边插入边统计：避免重复计算，降低时间复杂度

易错点

1. 模运算：所有加法、乘法运算后都要取模
2. 负数取模：减法后可能为负，需要加 \text{MOD} 再取模
3. 初始化：f[0] = 1 和 f[a[1]] = 1 都要初始化
4. 边界处理：sum[i] 统计时注意不要越界

完整 AC 代码

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)
#define debug(x) cerr << #x << " = " << (x) << endl

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

int n, a[MAXN];

long long qpow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

long long C(int n, int m) {
    if (m > n || m < 0) return 0;
    long long num = 1, den = 1;
    for (int i = 0; i < m; i++) {
        num = num * (n - i) % MOD;
        den = den * (i + 1) % MOD;
    }
    return num * qpow(den, MOD - 2) % MOD;
}

int qpow2(int b) {
    if (!b) return 1;
    int res = qpow2(b >> 1);
    res = (1ll * res * res) % MOD;
    if (b & 1) (res <<= 1) %= MOD;
    return res;
}

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

    bool allOne = true;
    for (int i = 1; i <= n; i++) {
        if (a[i] != 1) {
            allOne = false;
            break;
        }
    }

    if (allOne) {
        long long ans = qpow(2, n);
        ans = (ans - 1 - n - C(n, 2) % MOD + 2LL * MOD) % MOD;
        cout << ans << endl;
        return;
    }

    if (n <= 20) {
        long long ans = 0;

        function<void(int, int, int, int)> dfs = [&](int pos, int cnt, int sum, int maxval) {
            if (pos == n + 1) {
                if (cnt >= 3 && sum > 2 * maxval) {
                    ans++;
                    ans %= MOD;
                }
                return;
            }
            dfs(pos + 1, cnt, sum, maxval);
            dfs(pos + 1, cnt + 1, sum + a[pos], max(maxval, a[pos]));
        };

        dfs(1, 0, 0, 0);
        cout << ans << endl;

    } else {
        int f[MAXV], sum[MAXN];
        memset(f, 0, sizeof(f));
        memset(sum, 0, sizeof(sum));

        sort(a + 1, a + n + 1);

        f[a[1]] = f[0] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = MAXV - 1; j >= a[i]; j--) {
                (f[j] += f[j - a[i]]) %= MOD;
            }
            for (int j = 0; j <= a[i + 1]; j++) {
                (sum[i] += f[j]) %= MOD;
            }
        }

        int ans = 0;
        for (int i = 3; i <= n; i++) {
            (ans += (qpow2(i - 1) - sum[i - 1] + MOD) % MOD) %= MOD;
        }

        cout << ans << endl;
    }
}

signed main() {
    //file(polygon);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    //fclose;
    return 0;
}

总结

本题通过数据分层实现不同算法：

• 特殊性质（全为 1）用组合数学
• 小数据用暴力
• 大数据用容斥优化

核心是理解：枚举最大值后，问题转化为从剩余木棍中选择使得和满足条件的方案数统计问题，使用容斥原理 = 总方案数 - 不合法方案数。

温馨提示

注意事项:

1. 比赛的时候一定要检查有没有加 freopen, 如果没加的话就加上，加上了之后写代码时先注释掉，最后取消注释的时候一定要再编译一遍！（我同学已经因为这个吃亏了）
2. 比赛写到最后1小时的时候，如果别的题没有思路，就先给已经写过的题做数据分层，根据不同范围分析暴力枚举，深度优先搜索(Depth-First Search, DFS)等算法

解题技巧

1. 可以根据数据范围来猜测算法 时间/空间 复杂度 然后再根据复杂度选取合适的算法
2. 要多观察特殊性质，有时可以通过特殊性质推导出正解，也可以通过特殊性质进行混分，比赛总是分越多拿奖概率越高