LibreOJ 6433 「PKUSC2018」最大前缀和

期望还乘 n!……极其迷惑……
所以实际上就是统计所有排列的最大前缀和之和。

考虑把得到的排列的前缀和以最大的那一项分割为两个排列，那么如果单取后一半的话，每一项的前缀和一定都 ≤0（否则拼起来就会出现更大的前缀和）。
于是考虑设两个状态 fS,gS，分别表示在集合 S 中的数的排列的最大前缀和为 sumS 的方案数和在集合 S 中的排列的前缀和都 ≤0 的方案数。
其中 sumS=∑i∈Sai。

显然 g 更容易转移。
gS=∑i∈Sg∁S{i} (sumS≤0)

然后考虑 f，可以通过在排列前面加数的方式转移。
fS⋃{k}←fS⋃{k}+fS (k∉S,sumS>0)

如果 sumS≤0，那么就会出现更大的前缀和（即新加的 k）。

然后随手统计答案就完事了。

代码：

#include <cstdio>
#define lowbit(x) ((x) & -(x))
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);
}