记录编号	609197	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4195.[CSP-J 2025 T4]多边形	最终得分	100
用户昵称	金牌教师王艳芳	是否通过	通过
代码语言	C++	运行时间	0.489 s
提交时间	2025-11-02 22:49:27	内存使用	3.74 MiB

#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int a[5005];
int ps[5005];
int p2[5005];
int dp[5005];
int main(){
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    int n,i,j,s,ma,ans=0;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    ps[0]=0;
    for(i=1;i<=n;i++)ps[i]=ps[i-1]+a[i-1];
    p2[0]=1;
    for(i=1;i<=n;i++)p2[i]=(p2[i-1]*2)%MOD;
    ma=a[n-1];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(j=0;j<=n-2;j++){
        int aj=a[j];
        for(s=ma;s>=aj;s--){
            dp[s]=(dp[s]+dp[s-aj])%MOD;
        }
        int i_j=j+1;
        if(i_j<2)continue;
        int X=a[i_j];
        int psi=ps[i_j];
        if(psi<=X)continue;
        int S=0;
        for(s=0;s<=X;s++){
            S=(S+dp[s])%MOD;
        }
        int con=(p2[i_j]-S)%MOD;
        ans=(ans+con)%MOD;
    }
    ans=(ans+MOD)%MOD;
    cout<<ans<<endl;
    return 0;
}