自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 22:10:05，当前版本为作者最后更新于2019-12-08 15:06:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一丶前言

为了方便，定义/说明一些东西：

若存在多个$p$使得$\sum_{i=1}^{p}{a_i}$最大，默认最大的一个$p$是它的最大前缀和。

$U$表示全集

真后缀的含义即为除了整体以外的后缀

二丶思路

题目大意很清楚了吧，就是求$n$个数所有排列的最大前缀和之和，答案对$998244353$取模。

既然要求最大前缀和，我们先看看最大前缀和有些什么性质，假设$\sum_{i=1}^{p}a_i$是最大前缀和，那么：

1. 不存在$x(1<x<=p)$，使得$\sum_{i=x}^{p}a_i<0$，即没有任何一段真后缀和$<0$（不然我们把这一段舍去答案就更大了）

2. 不存在$x(p<x<=n)$，使得$\sum_{i=p+1}^{x}a_i>=0$，即没有任何一段前缀和$>=0$（否则我们把这一段加上之后更优）

显然条件$1$只跟前$p$个数有关，条件2只跟后$n-p$个数有关，因此我们考虑分开$DP$：

假设$f[S]$是集合$S$为最大前缀和时，集合$S$的排列满足条件$1$的方案。

$g[U$^$S]$是集合$S$为最大前缀和时，集合$U-S$的排列满足条件$2$的方案数。

并假设$sum[S]=\sum_{i\in S}a_i$

所以$ans=\sum_{S\subset U}sum[S]*f[S]*g[U-S]$，问题就在于如何求$f$和$g$了

我们假设$f$是从后面往前面加数，$g$是从前面往后面加数（注意理解这句话），那么$g$的$DP$方程就很简单了：

$g[S|u]+=g[S](sum[S|u]<0)$ （因为我们是从前往后加数，加完一个数之后我们只用判断当前前缀的和是否$<0$就行了）

以此类推，$f$的$DP$方程貌似也很类似，就是：

$f[S|u]+=f[S](sum[S|u]>=0)$

但是这样只能拿到$55$分，为什么呢？因为我们说的是没有任何一段真后缀和 $<0$，而不是后缀，所以这样会漏掉一部分。

那我们稍稍改一改就行了，我的方法是假设一个$f[S][0/1]$：

$f[S][0]$表示$sum[S]<0$，但它的任何真后缀的和都$>=0$的方案数。

$f[S][1]$则是$sum[S]>=0$的情况，且它的任何真后缀都$>=0$的方案数。

$DP$方程也稍稍改改就好了：

$f[S|u][0]+=f[S][1](sum[S|u]<0)$

$f[S|u][1]+=f[S][1](sum[S|u]>=0)$

则$ans=\sum_{S \subset U}(f[S][0]+f[S][1])* sum[S]*g[U$^$S]$

三丶代码

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define N 21
#define mod 998244353
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline ll Z(ll x){return x>=mod?x-mod:x;}
ll sum[1<<N];ll f[1<<N][2],g[1<<N];
ll n,a[N];
int main()
{
	n=read();
	for(register ll i=1;i<=n;i++)a[i]=read();
	for(register ll i=0;i<(1<<n);i++)
	{
		for(register ll j=1;j<=n;j++)
		{
			if(i&(1<<(j-1)))sum[i]=sum[i]+a[j];
		}
	}
	for(register ll i=1;i<=n;i++)if(a[i]<0)f[1<<(i-1)][0]=1;else f[1<<(i-1)][1]=1;//初始化
	for(register ll i=1;i<(1<<n);i++)
	{
		ll S=i;
		for(register ll j=1;j<=n;j++)
		{
			if(S&(1<<(j-1)))continue;
			ll T=S|(1<<(j-1));
			if(sum[T]>=0)f[T][1]=Z(f[T][1]+f[S][1]);
			else f[T][0]=Z(f[T][0]+f[S][1]);
		}
	}
	g[0]=1;
	for(register ll i=0;i<(1<<n);i++)
	{
		ll S=i;if(!g[S])continue;
		for(register ll j=1;j<=n;j++)
		{
			if(S&(1<<(j-1)))continue;
			ll T=S|(1<<(j-1));
			if(sum[T]<0)g[T]=Z(g[T]+g[S]);
		}
	}
	
	ll U=(1<<n)-1,ans=0;
	for(register ll i=1;i<=U;i++)
	{
		ans=Z(ans+Z(sum[i]%mod+mod)*Z(f[i][0]+f[i][1])%mod*g[U^i]%mod);
	}
	printf("%lld\n",ans);
	return 0;
}
/*
3
0 1 -2
*/

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!