期望还乘 \(n!\)……极其迷惑……
所以实际上就是统计所有排列的最大前缀和之和。
考虑把得到的排列的前缀和以最大的那一项分割为两个排列，那么如果单取后一半的话，每一项的前缀和一定都 \(\le 0\)（否则拼起来就会出现更大的前缀和）。
于是考虑设两个状态 \(f_S,g_S\)，分别表示在集合 \(S\) 中的数的排列的最大前缀和为 \(sum_S\) 的方案数和在集合 \(S\) 中的排列的前缀和都 \(\le 0\) 的方案数。
其中 \(sum_S = \sum\limits_{i \in S} a_i\)。
显然 \(g\) 更容易转移。
\[g_{S} = \sum\limits_{i \in S} g_{\complement_S \{i\}}\ (sum_S \le 0)\]
然后考虑 \(f\)，可以通过在排列前面加数的方式转移。
\[f_{S\bigcup\{k\}} \gets f_{S\bigcup\{k\}} + f_{S}\ (k \not \in S,sum_S > 0)\] 如果 \(sum_S \le 0\)，那么就会出现更大的前缀和（即新加的 \(k\)）。
然后随手统计答案就完事了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const int N = 20;
const int mod = 998244353;
int n,a[N + 5],full;
int lg[(1 << N) + 5];
long long sum[(1 << N) + 5];
int f[(1 << N) + 5],g[(1 << N) + 5],ans;
int main()
{
scanf("%d",&n),full = (1 << n) - 1;
for(register int i = 2;i <= full;++i)
lg[i] = lg[i >> 1] + 1;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= full;++i)
sum[i] = sum[i ^ lowbit(i)] + a[lg[lowbit(i)] + 1];
for(register int i = 1;i <= n;++i)
f[1 << i - 1] = 1;
g[0] = 1;
for(register int i = 0;i <= full;++i)
if(sum[i] > 0)
for(register int j = 1;j <= n;++j)
if(!((1 << j - 1) & i))
f[i | (1 << j - 1)] = (f[i | (1 << j - 1)] + f[i]) % mod;
for(register int i = 0;i <= full;++i)
for(register int j = 1;j <= n;++j)
if(!((1 << j - 1) & i) && sum[i | (1 << j - 1)] <= 0)
g[i | (1 << j - 1)] = (g[i | (1 << j - 1)] + g[i]) % mod;
for(register int i = 0;i <= full;++i)
ans = (ans + (long long)f[i] * g[full ^ i] % mod * (sum[i] + mod) % mod) % mod;
printf("%d\n",ans);
}