题目分析：
容易想到若集合$S$为前缀时，$S$外的所有元素的排列的前缀是小于$0$的，DP可以做到，令排列前缀个数小于0的是g[S].
令f[S]表示$S$是前缀，转移可以通过在前面插入元素完成。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 25; 5 6 const int mod = 998244353; 7 8 int n; 9 int a[maxn]; 10 int f[1<<20],g[1<<20],sum[1<<20],arr[1<<20]; 11 12 void read(){ 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 15 } 16 17 void dfs(int now){ 18 if(f[now]) return; 19 for(int i=0;i<n;i++){ 20 if((1<<i)&now){ 21 if(f[now-(1<<i)]) sum[now] = sum[now-(1<<i)]+a[i+1]; 22 else dfs(now-(1<<i)),sum[now] = sum[now-(1<<i)]+a[i+1]; 23 f[now] = 1; break; 24 } 25 } 26 } 27 28 int dfs2(int now){ 29 if(arr[now]) return f[now]; 30 arr[now] = 1; 31 for(int i=1;i<=n;i++){ 32 if((1<<i-1)&now){ 33 int z = dfs2(now-(1<<i-1)); 34 if(sum[now-(1<<i-1)] >= 0) f[now] += z,f[now] %= mod; 35 } 36 } 37 return f[now]; 38 } 39 40 int dfs3(int now){ 41 if(arr[now]) return g[now]; 42 arr[now] = 1; 43 for(int i=1;i<=n;i++){ 44 if((1<<i-1)&now){ 45 int z = dfs3(now-(1<<i-1)); 46 if(sum[now] < 0) g[now] += z,g[now]%=mod; 47 } 48 } 49 return g[now]; 50 } 51 52 void work(){ 53 f[0] = 1;for(int i=1;i<(1<<n);i++) dfs(i); 54 memset(f,0,sizeof(f)); 55 arr[0] = 1; f[0] = 1; 56 dfs2((1<<n)-1); 57 memset(arr,0,sizeof(arr)); 58 arr[0] = 1; g[0] = 1; 59 dfs3((1<<n)-1); 60 int res = 0; 61 for(int i=0;i<(1<<n);i++){ 62 res += (1ll*sum[i]*((1ll*f[i]*g[(1<<n)-1-i])%mod))%mod; 63 res %= mod; 64 } 65 res += mod; res %= mod; 66 printf("%d",res); 67 } 68 69 int main(){ 70 read(); 71 work(); 72 return 0; 73 }