「PKUSC2018」最大前缀和 LOJ#6433&BZOJ5369

分析：

这个题非常的棒，目测如果去了能AC…

我们考虑一个序列是如何构成的——一个后缀>0的序列，和一个前缀<0的序列

问题可以简化为求出当前缀和为状态S的所有数的和的时候，S满足后缀>=0的方案数和((1<<n)-1)^S满足前缀<0的方案数

那么可以写出方程，sum[S]表示状态S的和，f[S]表示由S构成的序列满足所有后缀>=0的方案数，g[S]表示由S构成的序列满足所有前缀<0的方案数

转移：f[S]=(f[S]+f[S^(1<<i-1)]),g[S]=(g[S]+g[S^(1<<i-1)])具体特判看代码。

注意：f[S]表示的一定是>=0，=不能省，很关键。不然的话，状态会缺很多。

神题，目测区分度很大…相比之下，比T1不知道高到哪里去了…

外加上Orz tangyunkai1 230虐场，（估计我也就200…T3还是爆弹去吧…），有学上了…

附上代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
#define N 21
#define M 1<<20
#define ll long long
#define mod 998244353
ll f[M],g[M],sum[M];
int n,a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[1<<(i-1)]=1;
f[0]=1,g[0]=1,sum[0]=0;
for(int S=1;S<(1<<n);S++)
{
for(int i=1;i<=n;i++)
{
if(S&(1<<(i-1)))
{
sum[S]=sum[S^(1<<(i-1))]+a[i];
break;
}
}
}
for(int S=1;S<(1<<n);S++)
{
for(int i=1;i<=n;i++)
{
if(!(S&(1<<(i-1))))continue;
int s=S^(1<<(i-1));
if(sum[s]<=0)continue;
f[S]=(f[s]+f[S])%mod;
}
if(sum[S]<=0)
{
for(int i=1;i<=n;i++)
{
if(!(S&(1<<(i-1))))continue;
int s=(S^(1<<(i-1)));
g[S]=(g[S]+g[s])%mod;
}
}
}
ll ans=0;
for(int S=1;S<(1<<n);S++)
{
//printf("%d %d %d %d\n",S,sum[S],f[S],g[((1<<n)-1)^S]);
ans=(ans+(sum[S]*f[S]%mod*g[((1<<n)-1)^S])%mod)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}