luoguP5369 [PKUSC2018] 最大前缀和

题目

n<=20

题解

想了半天3位状态的折半，然后发现空间开不下（时间也不太行）

所以放弃思考，直接枚举答案

---

答案是a中的一个集合，设为S；记集合S的和为sum[S]

考虑当S确定时，有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况，记S为从前往后考虑，第一次出现最大ans的集合；记剩余部分为\(\bar S\)

那么考虑S和\(\bar S\)在序列上的情况，记前者组成的子段为L后者为R；
有L中任意真后缀的和>0，R中任意前缀的和<=0（否则S会变）

所以取到S的情况就是二者方案乘积，都可以用\(O(n2^n)\)状压不断加数求解（真后缀要特殊处理最后的全集，开两个状态搞）

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b; a<=c; a++)
#define fd(a,b,c) for (int a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;const int N=21;
const int twoN=1048576;
int T,n,K=11;
int a[N];
int sum[twoN];
int F[twoN],f[twoN],g[twoN];
ll ans;int main()
{
//	freopen("luogu5369.in","r",stdin);scanf("%d",&n);fo(i,1,n) scanf("%d",&a[i]);fo(s,1,(1<<n)-1){fo(i,1,n)if (s&(1<<(i-1))){sum[s]=sum[s-(1<<(i-1))]+a[i];break;}}F[0]=1;fo(s,0,(1<<n)-1-1){fo(i,1,n)if (!(s&(1<<(i-1)))){if (sum[s|(1<<(i-1))]>0)add(F[s|(1<<(i-1))],F[s]);add(f[s|(1<<(i-1))],F[s]);}}g[0]=1;fo(s,0,(1<<n)-1-1){fo(i,1,n)if (!(s&(1<<(i-1))) && sum[s|(1<<(i-1))]<=0)add(g[s|(1<<(i-1))],g[s]);}fo(s,1,(1<<n)-1){int s2=((1<<n)-1)^s;add(ans,1ll*f[s]*g[s2]%mod*sum[s]);}printf("%lld\n",(ans+mod)%mod);
}