氢酱算法周记 000 - Codeforces 1204E

Posted on By 二价氢

Natasha, Sasha and the Prefix Sums

链接

视频

YouTube / Bilibili

试题

Codeforces 1204E

试题大意

定义一个数列 $a$ 的最大前缀和为 $f(a)=\max(0,\max\limits_{1\le i\le |a|} \sum\limits_{1\le j\le i} a_j )$, 对于包含 $n$ 个+1与 $m$ 个 −1 的所有 $a$ ,求对应的 $f(a)$ 的和, 答案对998244853取模, $0\le n, m\le 2000$,时间限制2秒

一种思路

试题的作者使用了动态规划的做法来解决此题,但使用纯组合数学方法亦可解决此题.

考虑一个退化版问题,即对于包含 $n$ 个1与 $m$ 个−1的所有子串,前缀和最大值恰为 $x$ 的序列种数

对于这个问题,我们不妨继续简化情况,询问有 $n$ 个1与 $m$ 个-1的所有序列中,最大前缀和恰为 n-m 的情况种数

可以证明简化后问题的答案为 $C^{n+m}_m−C^{n+m}_{m−1}$ 即,序列的任意后缀中,1的个数不少于-1的个数,这个答案的证明可以参考卡塔兰数的证明方法。

那么,对于包含 $n$ 个1与 $m$ 个-1的所有子串,前缀和最大值恰为 $x$ 的序列种数,可以通过枚举最大值 $x$ 第一次出现的位置得到,如果假设位置是 $y$ 的话

可以知道这个前缀包含 $(x+y)/2$ 个+1与 $(y-x)/2$ 个-1 那么这个前缀的种数即使之前简化问题的解 $C^{y-1}_{(y-x)/2} - C^{y-1}_{(y-x)/2-1}$

而对于答案的后半部分,就是从这个位置开始数,遇到的-1个数不会少于遇到的1的个数,如果后半部分有 $p=n−(x+y)/2$ 个+1与 $q=m−(y−x)/2$ 个-1,答案就是 $C^{p+q}_{p} - C^{p+q}_{p-1}$

至此,可以得知,前缀和最大值为 $x$ 的序列方案数为

进一步枚举𝑥,可以得到问题的答案为

复杂度分析

我们枚举了 $x$ 与 $y$,其中$x=\Theta(n) ,y=\Theta(n)$,计算组合数在预处理后计常数复杂度,复杂度约为$O(n^2)$ 在Codeforces上,本题使用了249ms

代码

#include <bits/stdc++.h>
using namespace std;
 
const long long mod = 998244853;
const int maxn= 4000 + 5;
long long prod[maxn], iprod[maxn];
 
long long pmod(long long a, long long b) {
	long long ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ret;
}
 
long long C(long long n, long long m) {
	if (n < m) return 0;
	if (n < 0 || m < 0) return 0;
	return prod[n] * iprod[m] % mod * iprod[n - m] % mod;
}
 
long long f(long long m, long long n) {
	if (m < n) return 0;
	return (C(m + n, m) - C(m + n, m + 1) + mod) % mod;
}
 
long long sol(long long n, long long m) {
	long long cnt = 0;
	for (long long i = 1; i <= n; i++) {
		for (long long j = 0; j <= m && j <= i; j++) {
			long long ans1, ans2;
			ans1 = f(i - 1, j) * (i - j) % mod;
			ans2 = f(m - j, n - i);
			(cnt += ans1 * ans2 % mod) %= mod;
		}
	}
	return cnt;
}
 
int main() {
	int n, m;
	prod[0] = iprod[0] = 1;
	for (long long i = 1; i < maxn; i++) {
		prod[i] = prod[i - 1] * i % mod;
		iprod[i] = pmod(prod[i], mod - 2);
	}
	cin >> n >> m;
	cout << sol(n, m) << endl;
	return 0;
}