P5369 [PKUSC2018] 最大前缀和做题记录

x383494 / 2023-08-26 / 原文

题目传送门

题意

给定一列数 \(a_{1\dots n}\)，求其所有排列的最大前缀和之和，\(\bmod \ 998244353\)。\(n \le 20, \sum \lvert a_{i} \rvert \le 10^9\)。

思路

~~暴力 10pts 跑路~~

考虑钦定一些数，作为最大前缀和，求出此时的排列情况数。

\(n \le 20\)，可以状压。

具体做法

下文用 \(S\) 表示我们选择的数，同时（在不引起歧义的情况下）表示它对应的二进制数。

维护 \(\mathrm{mnbk[]},\mathrm{mxfr[]},\mathrm{mnrbk[]}\) 分别表示 \(S\) 最小后缀和 \(\ge 0\) 的排列方案数，最大前缀和 \(\lt 0\)，最小真后缀和 \(\ge 0\)（\(\lvert S \rvert =1\) 时方案数恒为 \(1\)）。

按二进制数值从小到大枚举 \(S\)。

\(\lvert S \rvert = 1\) 时：\(\mathrm{mnbk}\) 和 \(\mathrm{mxfr}\) 只要通过 \(\sum_{x \in S} x\) 即可判断为 \(1\) 还是 \(0\)，\(\mathrm{mnrbk}\) 恒为 \(1\)。
\(\lvert S \rvert \gt 1\) 时：枚举「开头」元素 \(x \in S\)，则 \(\mathrm{mnbk}(S) = \mathrm{mnrbk}(S) = \sum_{x \in S} \mathrm{mnbk}(S \ \mathrm{xor} \ x)\)，\(\mathrm{mxfr}(S)\) 同理。注意根据 \(\sum_{x \in S} x\) 的正负性特判 \(\mathrm{mnbk} \leftarrow 0\) 或 \(\mathrm{mxfr} \leftarrow 0\)。

代码

#include <iostream>
#include <algorithm>
#define UP(i,s,e) for(auto i=(s); i<(e); ++i)
#define pcnt(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
auto lowbit(int x){ return x&-x; }
using ll = long long;
using std::cin; using std::cout;
constexpr int N = 20, SIZ = 1<<N;
constexpr int MOD = 998244353;
namespace m{ // }{{{
int in, ia[N];
int mnbk[SIZ], mnrbk[SIZ], mxfr[SIZ], sum[SIZ];
void work(){
	cin >> in;
	UP(i, 0, in) cin >> ia[i];
	mxfr[0] = 1;
	UP(i, 1, 1<<in){
		int lbx = lowbit(i);
		if(lbx == i){
			sum[i] = ia[ctz(i)];
			mnbk[i] = sum[i] >= 0;
			mnrbk[i] = 1;
			mxfr[i] = sum[i] < 0;
		} else {
			sum[i] = sum[i^lbx] + sum[lbx];
			for(int j=i; j; ){
				int lj = lowbit(j);
				j ^= lj;
				if(sum[i] < 0){
					mxfr[i] += mxfr[i^lj];
					mxfr[i] %= MOD;
				} else {
					mnbk[i] += mnbk[i^lj];
					mnbk[i] %= MOD;
				}
				mnrbk[i] += mnbk[i^lj];
				mnrbk[i] %= MOD;
			}
		}
	}
	int ans = 0;
	UP(i, 1, 1<<in){
		ans += mnrbk[i] * 1ll * mxfr[((1<<in)-1)^i] % MOD * sum[i] % MOD;
		ans %= MOD;
	}
	cout << (ans+MOD)%MOD << '\n';
}
} // {}}}
int main(){m::work(); return 0;}