[PKUSC2018]最大前缀和

Luogu P5369

题目描述

小 C 是一个算法竞赛爱好者，有一天小 C 遇到了一个非常难的问题：求一个序列的最大子段和。

但是小 C 并不会做这个题，于是小 C 决定把序列随机打乱，然后取序列的最大前缀和作为答案。

小 C 是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 \(n!\) 后对 \(998244353\) 取模的值，显然这是个整数。

注：最大前缀和的定义：\(\forall i \in [1,n]\)，\(\sum_{j=1}^{i}a_j\)的最大值。

输入格式

第一行一个正整数 \(n\)，表示序列长度。

第二行 \(n\) 个数，表示原序列 \(a[1..n]\)，第 \(i\) 个数表示 \(a[i]\) 。

输出格式

输出一个非负整数，表示答案。

样例 #1

样例输入 #1

2
-1 2

样例输出 #1

3

提示

对于\(10\%\)的数据，有\(1\leq n\leq 9\)。

对于\(40\%\)的数据，有\(1\leq n\leq 15\)。

另有\(10\%\)的数据，满足\(a\)中最多只有一个负数。

另有\(10\%\)的数据，满足\(|a[i]|\leq 2\)。

对于\(100\%\)的数据，满足\(1\leq n\leq 20\)，\(\sum_{i=1}^{n}|a[i]|\leq 10^9\)。

Solution

首先是看题目要求，题意就是要求我们求出所有最大前缀和的和，这一点分析出来不难，但是很重要。然后是看到 \(1\le n \le 20\) 的超小数据范围，还有紫色的难度，可以猜出来这道题可以用状压 \(\text{DP}\) 来做。

对于一个数列的最大前缀和，设最大前缀和出现的位置为 \(k\) ，那么根据定义有： \([k,t]\) 的前缀和一定 \(<0\) （ \(t\) 为数列中 \(k\) 后的一个位置），因为如果不满足 \(<0\) 这一条件，那么最大前缀和选上这部分一定可以获得更优解，不符合最大前缀和的定义，因此一定满足。

据此，我们可以将数列分为两个部分。先定义 \(sum[i]\) 表示当选择的数的集合为 \(i\) 时，这些数的和，那么可以设 \(f[i]\) 表示选择的数集的和为 \(sum[i]\) 时的方案数， \(g[i]\) 表示选择的数集 \(i\) 的 \(sum[i]<0\) 的方案数。那么，根据这些定义，可知 \(ans=\sum_{i\in U} sum[i] \times f[i]\times g[\complement_U i]\) （ \(U\) 表示所有数字的集合，即全集）。

考虑如何计算 \(f\) 和 \(g\) 。 \(g\) 是很好找到的，因为 \(g\) 的来源就是自己原来的集合去掉任意一个数，如果将 \(g\) 用二进制表示的话，那么如果 (i>>j&1) （第 \(j\) 个数字状态为 \(1\) ，表示存在于集合中），那么 \(g[i]\) 即可从这一状态更新，即 g[i]+=g[i^(1<<j)] （表示将 \(j\) 个数字的状态改为 \(0\) 后的集合）。这样就把 \(g\) 维护出来了。相比于 \(g\) ， \(f\) 数组就不是很好维护，因为我们并不能很清晰的找到 \(f\) 的具体来源，但是稍微观察可以发现， \(f\) 的前驱不好找，但是后继很好找，即直接找到一个数往集合里面加就可以了，因此可以使用刷表法来替代填表，有 f[i|(1<<j]+=f[i] （将 \(j\) 位数字状态改为 \(1\) 并更新这个状态对应的 \(f\) 值）。

对于 \(sum\) ，只需要在开始的时候将所有的状态全部枚举一遍然后直接计算即可。因为 \(sum[i]\) 中的 \(i\) 是由二进制表示的，因此 \(sum[i]\) 的值可以从 \(sum[\text{lowbit}(i)]\) 和 \(sum[i \text{^} \text{lowbit}(i)]\) 转移得到，这样就避免了枚举带来的更大的时间复杂度。

这样一个算法的时间复杂度为 \(\text O(2^n)\) ，对于本题来说足够了。

注意需要开\(\text{long long}\) 。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a));
#define LL long long
using namespace std;
template<typename T> void read(T &k)
{
 	k=0;
	T flag=1;char b=getchar();
	while (b<'0' || b>'9') {flag=(b=='-')?-1:1;b=getchar();}
	while (b>='0' && b<='9') {k=(k<<3)+(k<<1)+(b^48);b=getchar();}
	k*=flag;
}
const LL _SIZE=20,MOD=998244353,_STATSIZE=(1<<20);
LL n;
LL sum[_STATSIZE+5],ans;
LL f[_STATSIZE+5],g[_STATSIZE+5];
LL lowbit(LL x) {return x&(-x);}
LL Add(LL x,LL y) {x=(x%MOD+y%MOD+MOD)%MOD; return (x+MOD)%MOD;}
LL Mul(LL x,LL y) {x=(x%MOD*y%MOD+MOD)%MOD; return (x+MOD)%MOD;}
int main()
{
	read(n);
	for (LL i=0;i<n;i++) read(sum[1<<i]),f[1<<i]=1;
	for (LL i=1;i<(LL)1<<n;i++) sum[i]=sum[lowbit(i)]+sum[i^lowbit(i)];
	g[0]=1;
	for (LL i=1;i<(LL)1<<n;i++)
		if (sum[i]>=0)
		{
			for (LL j=0;j<n;j++)
				if (!(i>>j&1)) f[i|(1<<j)]=Add(f[i|(1<<j)],f[i]);
		}
		else
		{
			for (LL j=0;j<n;j++)
				if ((i>>j&1)) g[i]=Add(g[i],g[i^(1<<j)]);
		}
	for (LL i=1;i<(LL)1<<n;i++) ans=Add(ans,Mul(f[i],Mul(g[((1<<n)-1)^i],sum[i])));
	printf("%lld\n",ans);
	return 0;
}

额外的一些经验

最开始在对 \(f\) 和 \(g\) 进行转移的那个循环里面，判定 \(sum\) 的那个 \(\text{if}\) 没有使用花括号，虽然 \(\text{if}\) 和 \(\text{else}\) 内都只有一个 \(\text{for}\) 循环，但是编译器在没有花括号的情况下会将最近的两个 \(\text{if}\) 和 \(\text{else}\) 看作一起，导致答案错误，所以在省略花括号压行的时候还是要小心。