题目
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);
}
标签:twoN,前缀,int,PKUSC2018,luoguP5369,fo,sum,define
From: https://www.cnblogs.com/gmh77/p/18387652