[ARC127E] Priority Queue

题目描述

题目传送门

思路

正着做比较困难，反着来。假设 $\{a\}$ 是我们最后剩下来的集合。

可以发现一个结论：$a$ 是一个单调上升序列肯定不劣。

这样我们可以从头开始加入数字。每一此 2 操作实际上可以与其之前的 1 操作抵消。所以我们无需考虑二操作。

由于我们可以证明 $a$ 单调升。可以设 $f_{i,j}$ 表示 $\{a\}$ 第 $i$ 位填 $1\sim j$ 的时候的答案。

显然有：

$$f_{i,j} = f_{i-1,j-1} + f_{i,j-1}$$

时间复杂度：$\mathcal{O}(ab)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 5010;
const ll mod = 998244353;

int n;
int c[MAXN], tot, cnt, a, b;
ll sum[MAXN][MAXN];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> a >> b;
	for (int i = 1; i <= a + b; i++) {
		cin >> c[++tot];
		if (c[tot] == 1) {
			c[tot] = ++cnt;
		} else {
			tot--;
			tot--;
		}
	}
	for (int i = 0; i <= a; i++) sum[0][i] = 1;
	for (int i = 1; i <= a - b; i++) {
		for (int j = 1; j <= c[i]; j++) {
			sum[i][j] = (sum[i][j - 1] + sum[i - 1][j - 1]) % mod;
		}
		for (int j = c[i] + 1; j <= a; j++)
			sum[i][j] = sum[i][c[i]];
	}
	cout << sum[a - b][c[a - b]] << endl;
	return 0;
}