D. Monocarp and the Set-Educational Codeforces Round 156 (Rated for Div. 2)

D. Monocarp and the Set

给出的一串字符串，<表示最小的数，>表示最大的数，？表示中间任意数，问最多有多少种数的排列。
分析：最小数摆放之后又会有新的最小数，最大数也一样，所以字符串从后往前看。i从后往前遍历，出现？表示除去最大最小还有i-2个数符合条件，所有(i-2)相乘就可以算出第一个答案(相当于*i，因为数组下标从0开始，输入字符只有n-1个)。
特殊情况：s[0]=?一定不存在，输出0；
之后m个修改不能单独计算，会超时，所以要在原ans上一除一乘。
1.快速幂
2.逆元
(a/b)%m不等于a%m/b%m，所以在处理两个大数相除的商模一个数时，需要使用逆元。
/逆元使用公式：(A/B) % MOD=A * inv(B) % MOD/
/逆元计算公式：inv(x)=qpow(x,MOD-2);/
这道题中 ans = ans * qpow(i, MOD - 2) % MOD;
这道题不使用逆元会WA，精度不够。

#include
#define int long long
const int MOD=998244353;
using namespace std;
int qpow(int base,int power)
{
    int ans=1;
    while(power){
        if(power&1) ans=ans*base%MOD;
        base=base*base%MOD;
        power>>=1;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio;cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    string s;cin>>s;
    int ans=1;
    for(int i=s.length()-1;i>=1;i--)
    {
        if(s[i]=='?') ans=ans*i%MOD;
    }
    cout << (s[0] == '?' ? 0 : ans) << '\n';

    while(m--)
    {
        int i;
		char c;
		cin >> i >> c;
		i--;
		if (i != 0 && s[i] == '?') 
		{
			ans = ans * qpow(i, MOD - 2) % MOD;
		}
		s[i]=c;
		if (i != 0 && s[i] == '?') 
		{
			ans = ans * i % MOD;
		}
		cout << (s[0] == '?' ? 0 : ans) << '\n';
    }
    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