「Bzoj 5369」「PKUSC2018」最大前缀和 (状压DP)

BZOJ 5369
题意：给定$n$长序列$a_i$，求任意该序列排列最大前缀和的和。

我们考虑状压。

最大前缀和性质即我们可以找到一个位置 $p$ ，使得在这之前的 $ i $ 都满足 $\text{sum} (i) \leq \text{sum} (p)$，在这之后的 $i$ 都满足 $\text{sum} (i) \geq \text{sum} (p)$

考虑集合 $S$ 的数组成最大前缀和的方案数，那么计算就是一个求贡献
那么设 $g(S)$ 为 $S$ 集合组成序列最大前缀和是 $\text{sum}(S)$ 的方案数
$f(S)$ 为 $S$ 集合组成序列的任意最大前缀和都小于 $0$ 的方案数。
则$g(S + i)=\sum g(S), f(S)=\sum f(S-i)$
那么最后答案就是$\sum f(S)g(C_US)\text{sum}(S)$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 998244353;

    LL n, maxd, a[25], sum[(1 << 21) + 5], f[(1 << 21) + 5], g[(1 << 21) + 5];

    void clean() {
    }
    int solve() {

        clean();
        cin >> n; maxd = (1 << n) - 1;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), g[(1 << (i - 1))] = 1;
        for (LL S = 0; S <= maxd; ++S) {
            for (LL i = 1; i <= n; ++i) if (S & (1 << (i - 1))) sum[S] = sum[S ^ (1 << (i - 1))] + a[i];
        }
        f[0] = 1;
        for (LL S = 0; S <= maxd; ++S) {
            if (sum[S] >= 0) {
                for (LL i = 1; i <= n; ++i) {
                    if (!(S & (1 << (i - 1)))) (g[S | (1 << (i - 1))] += g[S]) %= MO;
                }
            } else {
                for (LL i = 1; i <= n; ++i) {
                    if (S & (1 << (i - 1))) (f[S] += f[S ^ (1 << (i - 1))]) %= MO;
                }
            }
        }
        LL ans = 0;
        for (LL S = 0; S <= maxd; ++S) 
            (ans += (sum[S] + MO) * g[S] % MO * f[(~S) & maxd] % MO) %= MO;

        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}