CF1886D Monocarp and the Set 题解

#pragma GCC optimize(3) 
#include <bits/stdc++.h>
#define eb emplace_back
#define int long long
using namespace std;
const int N = 2000100, mod = 998244353;
char s[N];
int ksm(int a, int b, int c) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % c;
        }
        a = a * a % c;
        b >>= 1;
    }
    return ans;
}
signed main() {
    int n, m;
    scanf("%lld%lld%s", &n, &m, s + 1);
    int now = 1;
    for (int i = 3; i <= n; ++i) {
        if (s[i - 1] == '?') {
            now = now * (i - 2) % mod;
        }
    }
    if (s[1] != '?') {
    cout << now << '\n';
    } else {
        cout << "0\n";
    }
    while (m--) {
        int o; char x;
        cin >> o >> x;
        if (o > 1) {
        if (s[o] == '?') {
            now = now * ksm(o - 1, mod - 2, mod) % mod;
        }
        if ((s[o] = x) == '?') {
            now = now * (o - 1) % mod;
        }
        } else {
            s[o] = x;
        }
        if (s[1] != '?') {
            cout << now << '\n';
        } else {
            cout << "0\n";
        }
    }
    return 0;
}

/*



*/