题面

Loj

题解

感觉挺难的啊～

状压\(dp\)

首先，有一个性质

对于一个序列的最大前缀和\(\sum_{i=1}^{p} A[i]\)

显然对于每个\(\sum_{i=p+1}^{x}A[i](p+1 \leq x \leq n)<0\)

我们可以以\(p\)分成两个集合

\(n\leq 20\),所以状压一下

\(sum[i]\)表示当前状态表示的和

\(f[i]\)表示用当前状态的数,组成最大前缀和为\(sum[i]\)的方案数

\(g[i]\)表示当前状态的数，组成的序列，每个前缀和都\(<=0\)

怎么转移呢？

考虑\(g\)的转移：

如果\(sum[S|(1<<i)] <= 0\)

那么\(g[s|(1<<i)] += g[S]\)

显然把\(A[i]\)放在序列末尾，也满足条件。。

考虑\(f\)的转移：

如果\(sum[S] > 0\)

那么\(sum[S] += sum[S-(1<<j)](j \in S)\)

把\(A[i]\)放在序列首，满足条件

然后 \(ans = f[S] * g[S'] * sum[S]\)

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 21, Mod = 998244353;

int a[N], f[1<<N], g[1<<N], num[1<<N], sum[1<<N];

#define lowbit(x) (x&(-x))

template<class T> inline void Add(T &x, T y) {x += y; if (x >= Mod) x -= Mod;}

int main() {

	int n;

	read(n);

	int limit = 1<<n;

	for (int i = 0; i < n; i++) read(a[i]), num[1<<i] = a[i];

	for (int i = 0; i < limit; i++)

		sum[i] = (sum[i^lowbit(i)] + num[lowbit(i)]) % Mod;

	g[0] = 1;

	for (int S = 0; S < limit; S++)

		if (sum[S] <= 0)

			for (int i = 0; i < n; i++)

				if ((S >> i) & 1)

					Add(g[S], g[S^(1<<i)]);

	LL ans = 0;

	for (int i = 0; i < n; i++)

		f[1<<i] = 1;

	for (int S = 0; S < limit; S++) {

		if (sum[S] > 0)

			for (int i = 0; i < n; i++)

				if (!((S >> i) & 1))

					Add(f[S|(1<<i)], f[S]);

		Add(ans, 1ll * f[S] * g[(limit-1)^S] % Mod * (sum[S]+Mod) % Mod);

	}

	printf("%lld\n", ans);

	return 0;

}