PKUSC2018 | 最大前缀和

发布于 2019-11-24  136 次阅读


题目大意

求一个给定长度为n的数列的随机排列最大前缀和的期望,乘以n!后对 998244353 取模,满足 1 \leq n \leq 20

算法讲解

易知答案是每一种排列的答案之和,且由数据范围可知这大概是一道状压题。

考虑一个计数问题的基本思路:从“先枚举一个方案再计算当前方案的结果”,转化为“先枚举一个结果再计算对应的方案数”。所以我们开始着手于解决:当确定一个最大前缀的集合为 S 的时候,满足条件的方案数是多少。
从最大前缀和的最基本定义入手:设原序列为aS_i表示\sum_{x=1}^{i}a_x,则有:

    \[S_i \ is \ the \ biggest \ prefix\]

    \[\Leftrightarrow \ \forall j \leq i \ , S_i \leq S_j \ \&\& \ \forall i<j \ , S_i>S_j\]

    \[\Leftrightarrow \ \forall j \leq i \ , S_i - S_j \leq 0 \ \&\&\ \forall i<j \ , S_i - S_j > 0\]

于是想到可以将满足条件的方案数拆解成集合S\complement_a S的方案数之积以统计。设F_S表示由集合S重新排列构成的序列,满足每个后缀和都小于等于零的方案数;G_S表示由集合S重新排列,得到的序列满足每个前缀和都小于零的方案数。转移的话,考虑在满足前缀性质的序列后端加入一个数,并不影响已经确定的前缀性质;只需要产生的新前缀满足小于零的性质即可,反之亦然。

#include<cstdio>
const int N=1100000;
const int mod=998244353;
int n,lim,f[N],g[N],ans;
long long s[N];
int main(){
    scanf("%d",&n),lim=1<<n;
    for(int i=0,x;i<n;i++)scanf("%d",&x),s[1<<i]=x;
    for(int i=0;i<lim;i++)s[i]=s[i^i&-i]+s[i&-i];
    f[0]=g[0]=1;
    for(int x=0;x<lim;x++)
        for(int i=0;i<n;i++)
        if(!(x&1<<i)){
            if(s[x]>=0)(f[x|1<<i]+=f[x])%=mod;
            if(s[x|1<<i]<0)(g[x|1<<i]+=g[x])%=mod;}
    for(int i=0;i<lim;i++)
        (ans+=1ll*f[i]*g[lim-1^i]%mod*s[i]%mod)%=mod;
    printf("%d\n",(ans+mod)%mod);
}

血まみれからの方がさ,勝つ時にはカッコイイだろう.