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

Azure_F · 2025-11-01 13:16:51 · 题解

考虑对 a 排序，那么通过移项可将原条件转化成

于是我们考虑 dp，设 f _ {i, j} 表示选前 i 个数和 = j 的方案数（这里的 j 开到值域就行，原因见下），则 f 容易用背包 O(nV) 地 dp 出来。

那么对于每个 i \ge 3，我们钦定它为最大值，那么所有选前面木棍的长度 \le a _ i 的方案数就是

用 2 ^ {i - 1} 去减得到的就是 > 的方案数了。

代码：

#include<iostream>
#include<algorithm>

constexpr int N = 5000 + 5, V = 5000 + 1;
constexpr int MOD = 998244353;

int n, a[N], f[V], sum[N];

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

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

    std::cin >> n; 
    for(int i = 1; i <= n; ++i) std::cin >> a[i]; 
    std::sort(a + 1, a + n + 1);
    f[a[1]] = f[0] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = V - 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 += (fp(i - 1) - sum[i - 1] + MOD) % MOD) %= MOD;
    }
    std::cout << ans;

    return 0;
}