题解 P5369 【[PKUSC2018]最大前缀和】

· · 题解

状压DP.

令sum[i] = 集合 i 内所有数的和。

令f[i] = 集合 i 内的数组成的排列，最大前缀和 = sum[i] 的方案数。

令g[i] = 集合 i 内的数组成的排列，所有的最大前缀和都 < 0 的方案数。

显然ans = \Sigma sum[i] * f[i] * g[ALL-i],其中ALL表示全集。

实际上这个统计答案的方法可以这样理解：

枚举最大前缀和的集合S组成的排列作为前半部分，

让其它数组成排列的后半部分，

前后拼接之后的序列的最大前缀和 = 前半部分的最大前缀和， 也就是要让序列的后半部分所有的最大前缀和 < 0

那么，怎么DP f[i] 和 g[i]呢？

当$sum[i] >= 0$时,$g[i] = 0.

当sum[i] < 0时,g[i] =\Sigma g[i-j](j ∈ i)

考虑刷表，在集合$i$的排列**前**加入一个数$j(j∉i)$, 如果$sum[i] > 0$,那么$f[i+j] += f[i].

否则,f[i]不能对f[i+j]产生任何贡献。

空间复杂度$O(2^n)$,时间复杂度$O(n2^n).

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
    LL x = 0,f = 1; char c = getchar();
    while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
    while (isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}
inline void write(LL x){
    if (x < 0) putchar('-'),x = -x;
    if (x > 9) write(x/10); putchar(x%10+'0');
}
inline void writeln(LL x){ write(x),putchar('\n'); }
const int P = 998244353,N = 20 + 5,L = 1<<20;
inline int add(int x,int y){ return (x+=y)>=P?x-P:x; }
inline int mul(LL x,int y){ return x*y-x*y/P*P; }
int n,l,f[L],g[L],ans; LL sum[L];
int main(){
    int i,j;
    n = read(),l = 1<<n;
    for (i = 0; i < n; ++i) sum[1<<i] = read(),f[1<<i] = 1;
    for (i = 1; i < l; ++i) sum[i] = sum[i^(i&-i)] + sum[i&-i];
    for (g[0] = i = 1; i < l; ++i) if (sum[i] >= 0)
        { for (j = 0; j < n; ++j) if (!(i>>j&1)) f[i|(1<<j)] = add(f[i|(1<<j)],f[i]); }
        else{ for (j = 0; j < n; ++j) if (i>>j&1) g[i] = add(g[i],g[i^(1<<j)]); }
    for (i = 1; i < l; ++i) ans = add(ans,mul(mul(sum[i]%P,f[i]),g[(l-1)^i])),ans = (ans % P + P) % P;
    writeln(ans);
    return 0;
}