先规定一些东西:
若存在多个 \(p\) 使得 \(\sum_{i=1}^{p}{a_i}\) 最大,默认最大(即最靠右)的一个 \(p\) 是它的最大前缀和的位置。
\(U\) 表示全集。
假设 \(p\) 是最大前缀和的位置,则说明不存在 \(1\lt x\le p\) 满足 \(\sum_{i=x}^{p}a_i\lt 0\),否则去掉这段答案不会变小。并且不存在 \(p\lt x\le n\) 满足 \(\sum_{i=p+1}^{x}a_i\ge0\),否则我们把这一段加上之后不会更劣。
而且数据范围那么小就考虑状压。
令 \(sum_i\) 表示集合 \(i\) 内所有数的和,\(f_i\) 表示集合 \(i\) 内的数组成的排列,最大前缀和 \(=sum_i\) 的方案数,\(g_i\) 表示集合 \(i\) 内的数组成的排列,所有的最大前缀和都 \(\lt0\) 的方案数。
显然最终答案为 \(\sum_i sum_i\times f_i\times g_{U-i}\)
先考虑如何求出 \(g_i\)。
当 \(sum_i\ge0\) 时,\(g_i=0\)。否则 \(g_i=\sum\limits_{j\in i}g_{i-j}\)。
然后 \(f_i\) 的话考虑刷表,在集合 \(i\) 的排列前加入一个数 \(j\)(\(j\notin i\))。
如果 \(sum_i\ge0\),那么 \(f_{i+j}+=f_i\),否则 \(f_i\) 没有贡献。
时间复杂度 \(\mathcal O(n2^n)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20, M = 1 << N, mod = 998244353;
int n, m;
int a[N];
ll sum[M]; int f[M], g[M];
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int main() {
scanf("%d", &n), m = 1 << n;
for (int i = 0; i < n; ++i) scanf("%d", &a[i]), sum[1 << i] = a[i], f[1 << i] = 1;
for (int i = 1; i < m; ++i) sum[i] = sum[i ^ (i & -i)] + sum[i & -i];
g[0] = 1;
for (int i = 1; i < m; ++i) {
if (sum[i] >= 0) {
for (int j = 0; j < n; ++j) if (!(i >> j & 1)) add(f[i | (1 << j)], f[i]);
}
else {
for (int j = 0; j < n; ++j) if (i >> j & 1) add(g[i], g[i ^ (1 << j)]);
}
}
int ans = 0;
for (int i = 1; i < m; ++i) add(ans, sum[i] * f[i] % mod * g[(m - 1) ^ i] % mod);
printf("%d", ans);
return 0;
}
标签:ge0,洛谷,前缀,int,sum,lt,P5369,mod
From: https://www.cnblogs.com/Kobe303/p/16846983.html