题意
有一个大小为\(n\)的排列，以某种顺序插入一个集合中，给出一个长度为\(n-1\)的字符串，第\(i\)位表示第\(i+1\)个插入的数在已有集合中的情况，\(<\)为最小，\(>\)为最大，\(?\)为其他情况，给出q个单次修改，每次修改后询问其顺序的可能数。
思路
先考虑静态，设当前为str[i],正在插入第\(i+1\)个数，则说明前面有\(i\)个数。若当前位为>或<，则说明该数在目前唯一确定；若为?，则共有\(i-1\)个空可插入，方案数应\(*(i-1)\)。在\(O(n)\)的时间内可预处理完毕。
考虑动态，因为某一位的情况没有后效性影响，因此可以\(O(1)\)动态维护每次方案，注意有模数，在除法时要使用逆元。
Code
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;
const ll mod = 998244353ll;
void work()
{
cin >> n >> m;
string a;
cin >> a;
auto pw = [&](ll base, ll x)
{
ll ans = 1;
while (x)
{
if (x & 1)
ans = (ans * base) % mod;
x >>= 1;
base = (base * base) % mod;
}
return ans;
};
ll ans = 1, bj = 1;
for (int i = 0; i < n; i++)
if (a[i] == '?')
{
if (i == 0)
bj = 0;
else
ans = (ans * i) % mod;
}
cout << ans * bj << endl;
char ch;
for (int i = 0, q; i < m; i++)
{
cin >> q >> ch;
if (q == 1 && ch != '?')
bj = 1;
else if (q == 1 && ch == '?')
bj = 0;
else
{
if (a[q - 1] == '?' && ch != '?')
ans = (ans * pw(q - 1, mod - 2) % mod);
else if (a[q - 1] != '?' && ch == '?')
ans = (ans * (q - 1)) % mod;
}
a[q - 1] = ch;
cout << ans * bj << endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
work();
}
|