P5369

· · 个人记录

[PKUSC2018]最大前缀和

状压 DP。

期望值乘上 n! 相当于乘上全排列，即所有可能的序列的方案数。

于是最后要求的答案就是所有排列的最大前缀和的和。

然后定义两个状态 f_i 和 g_i，分别表示使用集合 i 中的数的排列中，最大前缀和 =sum_i 或 <0 的方案数。

然后两个状态可以组成答案：

Ans=\sum sum_i\cdot f_i\cdot g_{\complement_Ui}

简单来说，就是 f_i 表示了最大前缀和为 sum_i 的全部排列情况，将这个状态内的数前置，剩下的数排在后面，并且所有的前缀和都 <0，拼在一起自然不会影响整个序列的最大前缀和为 sum_i。

然后就是关于 f_i 和 g_i 的转移。

g_i=0(\forall sum_i\ge0) g_i=\sum g_{i-j}(\forall sum_i<0,j\in i)

因为插入的数的位置很影响 f_i 的转移，我们不妨设这个数插入了第一个位置，这样其他数插入第一个位置的情况会在其他时候转移，不会重复或漏解，故不需要关心。

那么此时，f_i 可以这样转移：

f_{i+j}+=f_i(\forall j\notin i)

时间复杂度 O(n\cdot2^n)。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=22,mo=998244353;

ll n,ans;

ll sum[1<<N],f[1<<N],g[1<<N];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        sum[1<<(i-1)]=read();f[1<<(i-1)]=1;
    }

    for(ll i=0;i<(1<<n);i++) {
        sum[i]=sum[i^(i&-i)]+sum[i&-i];
    }

    g[0]=1;

    for(ll i=0;i<(1<<n);i++) {
        if(sum[i]>=0) {
            for(ll j=1;j<=n;j++) {
                if(!((i>>(j-1))&1)) {
                    f[i|(1<<(j-1))]=(f[i|(1<<(j-1))]+f[i])%mo;
                }
            }
        }
        else {
            for(ll j=1;j<=n;j++) {
                if((i>>(j-1))&1) {
                    g[i]=(g[i]+g[i^(1<<(j-1))])%mo;
                }
            }
        }
    }

    for(ll i=0;i<(1<<n);i++) {
        ans=(ans+((((sum[i]%mo)*f[i]+mo)%mo)*g[((1<<n)-1)^i]+mo)%mo+mo)%mo;
    }

    write(ans);

    return 0;
}