「PKUSC2018」最大前缀和

题面

题解

可以想到枚举成为最大前缀和的一部分的数

设(sum_i=sumlimits_{jin i}a[j])

设(f_i)表示满足(i)的最大前缀和等于(sum_i)的方案数

转移：对于(forall k otin i, sum_i > 0)

则有

[f_{icup{k}} gets f_i ]

原理：我们考虑倒着插入数字，如果存在后缀(sum_{suf} > 0)就可以直接转移

设(g_i)表示满足(i)的所有前缀和都(leq 0)的方案数

转移：对于(forall k otin i, sum_{icup{k}} leq 0)

则有

[g_{icup {k}} gets g_i ]

[ herefore ans = sum_i sum_i f_i g_{complement_S i} ]

其中(complement_S i)表示(i)的补集

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define clear(x, y) memset(x, y, sizeof(x))

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != '-' && (!isdigit(ch))) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int N(21), Mod(998244353);
int n, a[1 << N], sum[1 << N];
int f[1 << N], g[1 << N], S, ans;

int main()
{
	S = 1 << (n = read()), g[0] = 1;
	for(RG int i = 0; i < n; i++) a[1 << i] = read();
	for(RG int i = 0; i < S; i++) sum[i] = sum[i ^ (i & -i)] + a[i & -i];
	for(RG int i = 0; i < S; i++) if(sum[i] <= 0)
		for(RG int j = 0; j < n; j++) if((i >> j) & 1)
			g[i] = (g[i] + g[i ^ (1 << j)]) % Mod;
	for(RG int i = 0; i < n; i++) f[1 << i] = 1;
	for(RG int i = 0; i < S; i++)
	{
		if(sum[i] > 0) for(RG int j = 0; j < n; j++) if(!((i >> j) & 1))
			f[i | (1 << j)] = (f[i | (1 << j)] + f[i]) % Mod;
		ans = (ans + 1ll * (sum[i] + Mod) * f[i] % Mod
				* g[(S - 1) ^ i] % Mod) % Mod;
	}
	printf("%d
", ans);
	return 0;
}