Loj#6433「PKUSC2018」最大前缀和（状态压缩DP）

题面

Loj

题解

先转化题意，其实这题在乘了$n!$以后就变成了全排列中的最大前缀和的和（有点拗口）。$n\leq20$，考虑状压$DP$

考虑一个最大前缀和$\sum\limits_{i=1}^pa_i$。

这个位置$p$是最大前缀和的右界当且仅当对$\forall r>p$有：$\sum\limits_{i=p+1}^ra_i\leq0$

---

设$sum_i$表示二进制状态$i$的代数和，方便转移

设$g_i$表示选了子集$i$后有多少种排列使得所有的前缀和都$<0$，于是有（从下转移而来）：

$$g[i] += g[i \oplus (1 << j)]\ (sum[i]\leq0,sum[i\oplus(1<<j)]\leq0)$$

设$f_i$表示选了子集$i$后有多少种排列使得最大前缀和$=sum_i$，于是有（向上转移）：

$$f[i \ | \ (1 << j)]+=f[i]\ (sum[i]>0)$$

则最后答案就是（$m\oplus i$表示$i$的补集）：

$$ans=\sum_{i\in S}sum_i\times f_i \times g_{m\oplus i}$$

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;

template<typename T>
void read(T &x) {
    int flag = 1; x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}

const int N = 22, P = 998244353;
int n, m, a[1 << N], f[1 << N], g[1 << N], sum[1 << N], ret;
int lb(int x) { return x & -x; }

int main () {
    read(n), m = (1 << n) - 1;
    for(int i = 0; i < n; ++i) read(a[1 << i]);
    for(int i = 0; i <= m; ++i)
        sum[i] = sum[i ^ lb(i)] + a[lb(i)];
    g[0] = 1;
    for(int i = 0; i < n; ++i) f[1 << i] = 1;
    for(int i = 0; i <= m; ++i) {
        if(sum[i] <= 0) {
            for(int j = 0; j < n; ++j)
                if((1 << j) & i && sum[i ^ (1 << j)] <= 0)
                    (g[i] += g[i ^ (1 << j)]) %= P;
        } 
    }
    for(int i = 0; i <= m; ++i) {
        if(sum[i] > 0) {
            for(int j = 0; j < n; ++j)
                if(!((1 << j) & i)) (f[i | (1 << j)] += f[i]) %= P;
        }
        (ret += 1ll * (sum[i] + P) % P * f[i] % P * g[m ^ i] % P) %= P;
    }
    printf("%d\n", ret);
    return 0;
}