Solution

$s u m_{s}$ 表示 $s$ 状态的所有数对应的和
设 $f_{s}$ 表示状态为 $s$ 的最大前缀和的方案数

part1

$f_{s ∣ (1 < < i)} + = f_{s} (s u m_{s} > 0)$
考虑在 $i$ 这个点后面放一个集合 $s$ ，得到一个集合：
$i (a_{0})$ $a_{1}$ $a_{2} . . . a_{n}$
$s u m_{s} > 0$ 保证了 $s u m_{0... n} > s u m_{0...0}$
因为 $f_{s}$ 保证了对于任意的 $i \leq n$ ，都有 $s u m_{1... i} < s u m_{1... n}$
所以 $f_{s ∣ (1 < < i)}$ 保证了对于任意的 $i \leq n$ ，都有 $s u m_{0... i} < s u m_{0... n}$

part2

设 $g_{s}$ 表示状态为 $s$ 的所有前缀都 $\leq 0$ 的方案数
$g_{s} + = g_{s^{(} 1 < < i)} (s u m_{s} \leq 0)$

part3

$a n s = \sum s u m_{s} f_{s} g_{(1 < < n) - 1 - s}$

Code

#include<cstdio>
const int N=1<<20,M=998244353;
int n,i,s,ans,f[N],g[N],sum[N],a[N],st;
inline void ADD(int &x,int y){x+=y;if(x>=M)x-=M;}
int main(){
	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%d",&a[1<<i]),f[1<<i]=1;
	st=(1<<n)-1;
	for (s=0;s<=st;s++) sum[s]=sum[s^(s&-s)]+a[s&-s];
	for (s=0;s<=st;s++)
		if (f[s] && sum[s]>0)
			for (i=st^s;i;i^=i&-i) ADD(f[s|(i&-i)],f[s]);
	g[0]=1;
	for (s=1;s<=st;s++)
		if (sum[s]<=0)
			for (i=s;i;i^=i&-i) ADD(g[s],g[s^(i&-i)]);
	for (s=0;s<=st;s++) ans=(1ll*sum[s]*f[s]%M*g[st^s]+ans)%M;
	printf("%d",(ans+M)%M);
}