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

· · 题解

考虑可以枚举每个边作为最长边的时候的情况。那么很自然就想到了排序。因为此题与顺序无关，并且排完序后只需要在当前木棍前面取就能保证当前的是最长边了。

那么把第 i 条边作为最长边有多少种情况呢？首先，我们有 2^{i-1} 种选法，只需要在这里排除掉一些不合法的情况就行了。不合法的情况分为两种：

  1. 前面选的边数量小于等于 1。
  2. 前面选的边数之和小于等于当前边的长度。

很显然我们满足第一个的都满足第二个，所以我们只关心第二个就行。

那么这一步就很简单了，使用一个背包 dp 记录下和为某个数有多少种选法即可。

代码实现的话，只需要注意快速幂即可。

#include <bits/stdc++.h>
#define MOD 998244353
#define int long long
using namespace std;
int ways[5005]={1};
int a[5005];
int qpow(int a,int b){
    int ret=1;
    while (b){
        if (b&1) ret=(ret*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ret;
}
signed main(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    int ans=0;
    for (int i=1;i<=n;i++){
        ans=(ans+qpow(2,i-1))%MOD;
        for (int j=0;j<=a[i];j++) ans=(ans+MOD-ways[j])%MOD;
        // cerr<<ans<<endl;
        for (int j=5000;j>=a[i];j--) ways[j]=(ways[j]+ways[j-a[i]])%MOD;
    }
    cout<<ans;
}