考虑对于一个序列，如果 Sp S p 是最大前缀和，那么对于p+1…n这个序列，需要满足任意前缀和均<=0.否则 Sp S p 一定不是最大前缀和。
sum[s]表示s子集的点的权值和。 f[s],表示选了s的点,sum[s]为最大前缀和的方案数 g[s],表示选了s的点,所有前缀和均<=0的方案数 那么最后答案就是 ∑sum[s]∗f[s]∗g[s¯¯¯] ∑ s u m [ s ] ∗ f [ s ] ∗ g [ s ¯ ] f[s]的转移，如果sum[s]>0,可以考虑在满足f[s]的方案最前面放一个没出现过的数，那么一定可以转移到f[s|bin[i]]。 g[s]的转移，可以考虑在后面再放一个i，如果sum[s|bin[i]]<0那么就可以转移到g[s|bin[i]| 复杂度 O(2nn) O ( 2 n n )
#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 25 #define mod 998244353 inline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } int n,a[N],sum[1100000],f[1100000],g[1100000],bin[N],ans=0; //f[s],选了s的点,sum[s]为最大前缀和的方案数 g[s],选了s的点,所有前缀和均<=0的方案数 inline void inc(int &x,int y){x+=y;x%=mod;} int main(){ // freopen("a.in","r",stdin); n=read();bin[0]=1;g[0]=1; for(int i=1;i<=n;++i) a[i]=read(),bin[i]=bin[i-1]<<1; for(int i=1;i<=n;++i){ f[bin[i-1]]=1; for(int s=0;s<bin[n];++s) if(s&bin[i-1]) inc(sum[s],a[i]); }for(int s=0;s<bin[n];++s){ if(sum[s]>0){ for(int i=0;i<n;++i) if(!(s&bin[i])) inc(f[s|bin[i]],f[s]);continue; }for(int i=0;i<n;++i) if(s&bin[i]) inc(g[s],g[s^bin[i]]); }for(int s=0;s<bin[n];++s) inc(ans,(ll)f[s]*sum[s]%mod*g[bin[n]-1^s]%mod); printf("%d\n",ans<0?ans+mod:ans); return 0; }