专栏文章

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

RRootSign
P14360题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minfnlu2
此快照首次捕获于
2025/12/02 01:38
3 个月前
此快照最后确认于
2025/12/02 01:38
3 个月前
查看原文

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

题目分析

给定 nn 根长度为 aia_i 的木棍，求有多少种选择方案使得选出的木棍能拼成多边形。
多边形条件：至少选 33 根木棍，且满足 ∑i=1mli>2×max⁡i=1mli\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i。
答案对 998244353998244353 取模。

数据范围分析

根据题目给出的测试点分布进行数据分层：
测试点nnmax⁡ai\max a_i策略
1-3≤3\leq 3≤10\leq 10暴力枚举
4-6≤10\leq 10≤100\leq 100暴力枚举
7-10≤20\leq 20≤100\leq 100暴力枚举
11-14≤500\leq 500≤100\leq 100容斥优化
15-17≤500\leq 500=1= 1组合数学
18-20≤5000\leq 5000=1= 1组合数学
21-25≤5000\leq 5000≤5000\leq 5000容斥优化

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

适用范围： ai=1a_i = 1 对所有 ii 成立
时间复杂度： O(n)O(n)
核心思想： 当所有木棍长度都是 11 时，选 kk 根木棍，最大值必为 11，条件变为： k>2×1⇒k>2k > 2 \times 1 \Rightarrow k > 2
即只要选择 ≥3\geq 3 根木棍即可。
答案公式： ans=∑k=3n(nk)=2n−1−n−(n2)\text{ans} = \sum_{k=3}^{n} \binom{n}{k} = 2^n - 1 - n - \binom{n}{2}
推导：
  • 总方案数：2n2^n
  • 减去选 00 根：11
  • 减去选 11 根：nn
  • 减去选 22 根：(n2)\binom{n}{2}
代码实现：
CPP
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≤20n \leq 20
时间复杂度： O(2n×n)O(2^n \times n)
核心思想： 直接 DFS 枚举所有子集，对每个子集判断是否满足条件。
对于每个位置可以选或不选，最终检查：
  1. 选出的木棍数量 ≥3\geq 3
  2. ∑li>2×max⁡li\sum l_i > 2 \times \max l_i
代码实现：
CPP
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>20n > 20 且非全 11
时间复杂度： O(n×V)O(n \times V)，其中 V=max⁡(ai)V = \max(a_i)
核心思想： 对于第 ii 根作为最大值，从前 i−1i-1 根任意选的方案数为 2i−12^{i-1}，减去不合法方案数。

关键思路

枚举每根木棍作为最大值 MM，需要满足：
  • 从前面的木棍中选若干根
  • 选出的木棍总和 SS 满足 S+M>2MS + M > 2M，即 S>MS > M
  • 至少选 22 根其他木棍（加上最大值共 33 根）
容斥原理：
  • 从前 i−1i-1 根任意选：2i−12^{i-1} 种方案
  • 不合法方案：选出的和 ≤M\leq M
则答案为： ans=∑i=3n(2i−1−不合法方案数)\text{ans} = \sum_{i=3}^{n} (2^{i-1} - \text{不合法方案数})

算法步骤

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

关键优化

为什么 sum[i]sum[i] 统计的是和 ≤a[i+1]\leq a[i+1]？
因为处理第 ii 根时，ff 数组包含了前 ii 根的所有组合。当第 i+1i+1 根作为最大值时，不合法方案就是从前 ii 根中选出和 ≤a[i+1]\leq a[i+1] 的方案。
初始化：
  • f[0]=1f[0] = 1：不选任何木棍（代表选 00 根的方案）
  • f[a[1]]=1f[a[1]] = 1：只选第一根
状态转移：
对于第 ii 根木棍：
  1. 更新背包：f[j]←f[j]+f[j−a[i]]f[j] \gets f[j] + f[j - a[i]]（从后往前）
  2. 统计不合法方案：sum[i]=∑j=0a[i+1]f[j]sum[i] = \sum_{j=0}^{a[i+1]} f[j]
快速幂计算 2k2^k：
使用递归 + 位运算优化，左移一位相当于乘 22。
CPP
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;
}

完整代码实现

CPP
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;
}

复杂度总结

算法时间复杂度空间复杂度测试点
组合数学O(n)O(n)O(1)O(1)15-20
暴力枚举O(2n×n)O(2^n \times n)O(n)O(n)1-10
容斥优化O(n×V)O(n \times V)O(V+n)O(V + n)11-14, 21-25
其中 V=max⁡(ai)≤5000V = \max(a_i) \leq 5000。

核心技巧总结

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

易错点

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

完整 AC 代码

CPP
#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. 要多观察特殊性质，有时可以通过特殊性质推导出正解，也可以通过特殊性质进行混分，比赛总是分越多拿奖概率越高

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...