专栏文章

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

AAzure_F
P14360题解参与者 21已保存评论 22

文章操作

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

当前评论
22 条
当前快照
1 份
快照标识符
@minfsstr
此快照首次捕获于
2025/12/02 01:42
3 个月前
此快照最后确认于
2025/12/02 01:42
3 个月前
查看原文
考虑对 aa 排序，那么通过移项可将原条件转化成
∑i=1m−1li>lm\sum _ {i = 1} ^ {m - 1} l _ i > l _ m
于是我们考虑 dp，设 fi,jf _ {i, j} 表示选前 ii 个数和 =j= j 的方案数（这里的 jj 开到值域就行，原因见下），则 ff 容易用背包 O(nV)O(nV) 地 dp 出来。
那么对于每个 i≥3i \ge 3，我们钦定它为最大值，那么所有选前面木棍的长度 ≤ai\le a _ i 的方案数就是
∑j=0aifi−1,j\sum _ {j = 0} ^ {a _ i} f _ {i - 1, j}
用 2i−12 ^ {i - 1} 去减得到的就是 >> 的方案数了。
代码：
CPP
#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;
}

评论

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

正在加载评论...