【数学】Monocarp and the Set—CF1886D

Monocarp and the Set—CF1886D
参考文章

思路

我们把添加数字的过程倒过来看，也就是对长度为 $n$ 的数组一个一个删除数字。那么 ${}^{\prime }{>}^{\prime }$、${}^{\prime }{<}^{\prime }$、${}^{\prime }{?}^{\prime }$ 就分别代表“删除最大的数字”、“删除最小的数字”、“删除一个不是最大值和最小值的数字”。

假设读入的字符串为 $s$。我们规定有效下标从 $2$ 开始，因为这样 $s_i$ 代表的就是“数组中元素个数为 $i$ 的时候从数组中删除一个元素”，符合人的思维，有利于后边写代码。

我们逆序遍历 $s$。如果 $s_i={}^{\prime }{>}^{\prime }$ 或 $s_i={}^{\prime }{<}^{\prime }$，那么显然这时候从数组中需要删除的数字一定是唯一的（删除最大值或最小值）；如果$s_i={}^{\prime }{?}^{\prime }$，因为这时候数组中元素个数为 $n$，所以除了不能删除最大值和最小值的话，我们能删除的数字的个数为 $i-2$。

易知 $res=$ “所有 $s_i={}^{\prime }{?}^{\prime }$ 时的 $i-2$ 的乘积”。

如果 $s_2={}^{\prime }{?}^{\prime }$ ，我们不能从两个数字中挑选一个不是最大值也不是最小值的数字，所以这时候我们直接判定 $res=0$（为什么不用考虑 $s_1={}^{\prime }{?}^{\prime }$ 的情况呢？因为题目规定第一次添加数字的时候不会“writes out a character”，所以自然也不用考虑数组中元素个数为 $1$ 的时候要删除最大值、最小值还是一个不是最大值也不是最小值的数字）。

至于 $m$ 次改变 $s$ 字符串的操作，很容易可以想到这样即可：

int idx; cin >> idx; idx ++;
string cc; cin >> cc;
if (idx >= 3 && s[idx] == '?') {
	res = res / (idx - 2);
}
s[idx] = cc[0];
if (idx >= 3 && s[idx] == '?') {
	res = res * (idx - 2) % mod;
}
cout << (s[2] != '?' ? res : 0) << "\n";
1
2
3
4
5
6
7
8
9
10

由于设计到了取模，那么第一个 if 语句中的 res = res / (idx - 2); 在相除的时候不一定会整除，那么我们就不能使用除法了。这里我们变除法为乘法，使用乘法逆元，把 res = res / (idx - 2); 改为 res = res * qpow(idx - 2, mod - 2, mod) % mod;。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;
const int mod = 998244353;

int n, m;

int qpow(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

void solve() {
	cin >> n >> m;
	string s; cin >> s;
	s = "  " + s;
	
	int res = 1;
	for (int i = n; i >= 3; i --) {
		if (s[i] == '?') {
			res = res * (i - 2) % mod;
		}
	}
	
	cout << (s[2] != '?' ? res : 0) << "\n";
	while (m --) {
		int idx; cin >> idx; idx ++;
		string cc; cin >> cc;
		if (idx >= 3 && s[idx] == '?') {
			res = res * qpow(idx - 2, mod - 2, mod) % mod;
		}
		s[idx] = cc[0];
		if (idx >= 3 && s[idx] == '?') {
			res = res * (idx - 2) % mod;
		}
		cout << (s[2] != '?' ? res : 0) << "\n";
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
//	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58