P5369 [PKUSC2018] 最大前缀和 题解

标签：前缀 后缀 题解 PKUSC2018 setminus maxn P5369 sum 最大

传送门

题目大意

给定一个序列，求任意重排 \(n!\) 中情况所以的最大非空前缀和的和。模 \(998244353\)。
\(n\e 20\)，\(\sum |a_i| \le 10^9\)

题目解析

考虑最大前缀和的性质，有：
对于最大前缀和部分，所有的 真 后缀大于等于零。（最大前缀和可能小于零）
对于不在最大前缀和的后半部分，所有的前缀和小于等于零。
证明略去，显然。
所以对于前后两部分 分开 状压 DP 即可。

先考虑后半部分。
从后往前选。设 \(g(S)\) 表示选了 \(S\) 这些数字的方案数量。
那么

\[g(S)=\sum_{i\not\in S} g(S \setminus i) \]

当然需要保证 \(\sum _{x\in S} x \ge0\)。

然后考虑前半部分。
从前向后选。
考虑到真后缀这个限制。
设 \(f(S,0/1)\) 表示选了 \(S\) 这些数字，所有后缀/所有真后缀 大于等于零的方案数。
有

\[f(S,0)=\sum_{i\not\in S} f(S \setminus i ,0),\sum _{x\in S} x \ge 0 \]

\[f(S,1)=\sum_{i\not\in S} f(S \setminus i ,0),\sum _{x\in S} x <0 \]

答案显然，就是

\[\sum_{S \sub U ,S\not = \varnothing} (f(S,0)+f(S,1)) g(U\setminus S) (\sum_{x\in S} x) \]

\(U\) 为全集。

时间复杂度 \(O(2^nn)\)

#define maxn 1200039
#define MOD 998244353
int n,m,a[39],p[maxn]; ll f[maxn][2],g[maxn],s[maxn];
int main(){
	fin>>n; m=(1<<n)-1; int i,j; ll ans=0;
	for(i=0;i<n;i++){ fin>>a[i],p[1<<i]=i; if(a[i]>=0) f[1<<i][0]=1; else f[1<<i][1]=1; }
	for(i=1;i<=m;i++) s[i]=s[i^(i&-i)]+a[p[i&-i]];
	g[0]=1;
	for(i=0;i<=m;i++) for(j=0;j<n;j++) if(!(i&(1<<j))){
		if(a[j]+s[i]>=0) f[i|(1<<j)][0]+=f[i][0],f[i|(1<<j)][0]%=MOD;
		else f[i|(1<<j)][1]+=f[i][0],f[i|(1<<j)][1]%=MOD,g[i|(1<<j)]+=g[i],g[i|(1<<j)]%=MOD;
	}
	for(i=1;i<=m;i++) ans+=(s[i]%MOD+MOD)%MOD*(f[i][1]+f[i][0])%MOD*g[m^i]%MOD,ans%=MOD;
	fin<<ans<<'\n'; return 0;
}

标签：前缀,后缀,题解,PKUSC2018,setminus,maxn,P5369,sum,最大
From： https://www.cnblogs.com/jiangtaizhe001/p/17582775.html