[LOJ 6433]「PKUSC2018」最大前缀和

Posted on | Edited on | In , | Views:

题目链接

LOJ 6433

前言

发现PKU好喜欢出概率期望dp啊，SCD1T2也是道概率期望dp。

做法

仔细观察一下最大前缀和的性质，令最大前缀和最后一个数是第i位，可以发现$[1,i]$这一段所有的后缀和都为正，(否则你减掉这一段显然可以得到一个更大的)，$[i+1,n]$这一段的前缀和都非正。
考虑状压dp，以$f[i]$表示选的数的集合是i，这个状态所有后缀和均为正的方案数，$g[i]$表示选的数的集合为i，这个状态所有前缀和均不正的方案数。
两个的转移是类似的，f可以看做是前缀和，反正首尾倒过来就边后缀和了。
枚举新加入一个数放在最后，如果它与前面所有的和是正的，那么$f[i|(1<<j-1)]+=f[i]$，否则$g[i|(1<<j-1)]+=g[i]$
最后枚举最大前缀和的集合，$ans+=sum[i]*f[i]*g[(1<<n)-1-i]$.

交上去发现wa了，再仔细读一遍题目，发现最大前缀和不能为空，也就是如果每一段前缀和都是负的，我们也要选一段最大的，而不是啥都不选。而我们上面的dp显然我发处理这种情况，因为f都是0。
而这种情况的最大前缀和也有非常好的性质，除了所有加起来是负的，其他所有的后缀也都是正的。
我们只要在dp一个f1即可，$f1[i]$表示选的数的集合是i，这个状态出整个串之外的所有后缀和均为正的方案数。
转移也很简单，枚举一个新加入的数放在最后，如果它与前面所有的和是负的，那么
$f1[i|(1<<j-1)]+=f[i]$即可。
最后统计答案的时候，如果f[i]为0，把f[i]改成f1[i]即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,ans; 
const int P=998244353;
int f[1<<20],g[1<<20],sum[1<<20],a[N],f1[1<<20];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b); 
}
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=0;i<(1<<n);i++){
        for (int j=1;j<=n;j++){
            if ((1<<j-1)&i) sum[i]+=a[j]; 
        }
    }
    f[0]=1;
    g[0]=1;
    for (int i=0;i<(1<<n);i++){
        for (int j=1;j<=n;j++){
            if (!((i>>j-1)&1)){
                int tow=i|(1<<j-1);
                if (sum[tow]>0) f[tow]=Inc(f[tow],f[i]);
                else g[tow]=Inc(g[tow],g[i]),f1[tow]=Inc(f1[tow],f[i]);
            }    
        }
    }
    for (int i=0;i<(1<<n);i++){
        if (f[i]==0) ans=Inc(ans,1ll*(sum[i]+P)*f1[i]%P*g[(1<<n)-1-i]%P);
        else ans=Inc(ans,1ll*sum[i]*f[i]%P*g[(1<<n)-1-i]%P);
    }
    
    printf("%d",ans);
    return 0;
}