分析
我们让每个数列在第一个取到最大前缀和的位置被统计到。
假设一个数列在\(pos\)处第一次取到最大前缀和，分析性质，有：
下标在\([1,pos]\)之间的数形成的数列的每个后缀和（不包括整个数列，因为要求非空）都大于\(0\)。
下标在\([pos+1,n]\)之间的数形成的数列的每个前缀和（包括整个数列）都小于等于\(0\)。
正确性显然。
所以我们可以把数列从\(pos\)分成两部分，分别算出各自的方案数再相乘。
\([1,pos]\)部分
令\(f[S]\)表示\(S\)中的数形成的每个后缀和都大于\(0\)的数列个数，考虑每次向一个数后面加一个满足条件的数列，有状态转移方程：
\[f[\{i\}+S]+=f[S]\ (i \notin S,\ sum[S]>0)
\]
\]
\([pos+1,n]\)部分
令\(g[S]\)表示\(S\)中的数形成的每个前缀和都小于等于\(0\)的数列个数，考虑每次向一个满足条件的数列后面加一个数，有状态转移方程：
\[g[S+\{i\}]+=g[S]\ (i \notin S,\ sum[S] \leq 0,\ sum[S+\{i\}] \leq 0)
\]
\]
统计答案的话好像没什么好说的。
代码
#include <bits/stdc++.h>
#define rin(i,a,b) for(int i=(a);i<=(b);++i)
#define irin(i,a,b) for(int i=(a);i>=(b);--i)
#define trav(i,a) for(int i=head[a];i;i=e[i].nxt)
#define Size(a) (int)a.size()
#define pb push_back
#define mkpr std::make_pair
#define fi first
#define se second
#define lowbit(a) ((a)&(-(a)))
typedef long long LL;
using std::cerr;
using std::endl;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MOD=998244353;
int n,a[25],b[1<<20],f[1<<20],g[1<<20];
LL sum[1<<20];
inline int add(int x,int y){
return x+y<MOD?x+y:x+y-MOD;
}
int main(){
n=read();
rin(i,1,n)a[i]=b[1<<(i-1)]=read(),f[1<<(i-1)]=1;
rin(i,1,(1<<n)-1)sum[i]=sum[i-lowbit(i)]+b[lowbit(i)];
rin(i,1,(1<<n)-1)if(sum[i]>0){
int r=(((1<<n)-1)^i);
while(r){
f[i|lowbit(r)]=add(f[i|lowbit(r)],f[i]);
r-=lowbit(r);
}
}
g[0]=1;
rin(i,0,(1<<n)-1)if(sum[i]<=0){
int r=(((1<<n)-1)^i);
while(r){
if(sum[i|lowbit(r)]<=0)g[i|lowbit(r)]=add(g[i|lowbit(r)],g[i]);
r-=lowbit(r);
}
}
int ans=0;
rin(i,0,(1<<n)-1)ans=(ans+1ll*sum[i]*f[i]%MOD*g[((1<<n)-1)^i])%MOD;
printf("%d\n",(ans%MOD+MOD)%MOD);
return 0;
}