做完这个题之后对状压dp有了一个新的了解...
一开始想到状压但并不知道如何状压，还是看了题解钻研之后才会的...
首先观察答案性质，发现一定有(p)使得(a[1...p])是最大前缀和且后面的任意(a[p+1...x])之和都(leq 0).
因为如果大于的话，就可以拿(a[1...x])来替换(a[1...p])，而答案更优。
故可以枚举最大前缀和的构成部分，即一个子集(T)
那么答案就等于(sum_{T subseteq S} sum_T * f_T * g_{S xor T})，
其中(sum_S)表示(S)这个子集的所有数的和，(f_S)表示(S)这些数所构成的最大前缀和恰为(sum_S)的方案数，(g_S)表示这些数所构成的最大前缀和(<0)的方案数。
那么接下来只要考虑如何转移(f)和(g)即可解决本题。
对于(f)，可以通过“向前塞元素”的方法来转移。
为什么呢？假设我们目前有一个集合(S)，整体的和(>0)，而又有一个未出现在(S)中的下标(i)，那么如果把(i)放在(S)前面，原来的最大前缀和即将会加上(a_i)，
即可以有更新(f_{Scup i} leftarrow f_{S})。
对于(g)也是同理，但我们将枚举哪个元素在最后一个位置。若整体的和(<=0)，那么对于剩下的满足条件，新的方案也应该满足条件，即有更新
(g_{Scup i} leftarrow g_{S})。
注意边界条件，即(g_0=1)，(f_{2^x}=1).
如此转移即可通过本题，注意要输出((ans+MOD)mod MOD).
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define LOG(...) fprintf (stderr, __VA_ARGS__)
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
const int INF = 0x3f3f3f3f, MOD = 998244353;
const LL INFL = 0x3f3f3f3f3f3f3f3fll;
const int N = 25, L = 1048600;
int n, a[N];
int f[L], sum[L], g[L];
/*
f[i]: i这个集合最大前缀和恰为sum[i]的方案数
g[i]: i这个集合最大前缀和<0的方案数
sum_{sum[i]*f[i]*g[ALL^i]}
f[i]: 考虑在前面接一个项a[k]
g[i]: 考虑在最后接一个项a[k]
*/
int main() {
#ifdef LiM_817
freopen ("input.txt", "r", stdin);
double cl = clock();
#endif
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < (1 << n); i++)
for (int j = 0; j < n; j++)
if (i & (1 << j)) (sum[i] += a[j]) %= MOD;
for (int i = 0; i < n; i++) f[(1 << i)] = 1;
g[0] = 1;
for (int i = 0; i < (1 << n); i++) {
if (sum[i] > 0) {
for (int j = 0; j < n; j++)
if (!(i & (1 << j)))
(f[i | (1 << j)] += f[i]) %= MOD;
} else {
for (int j = 0; j < n; j++)
if (i & (1 << j))
(g[i] += g[i ^ (1 << j)]) %= MOD;
}
}
int ans = 0, S = (1 << n) - 1;
for (int i = 0; i < (1 << n); i++)
(ans += 1LL * sum[i] * f[i] % MOD * g[S ^ i] % MOD) %= MOD;
cout << (ans + MOD) % MOD << endl;
#ifdef LiM_817
cerr << fixed << setprecision(2) << "Time ellapsed: " << ((double)(clock() - cl) / CLOCKS_PER_SEC) << "s
";
#endif
return 0;
}