CF1886D. Monocarp and the Set 题解

· · 题解

建议标签：数学。

建议难度：普及/提高-。

思路

这个题目非常有意思。

当您苦思冥想都想不出来怎么正着做的时候，不妨把问题反过来想想。

题中说是加数，我们就可以把所有的操作反过来，从 n 个数字中不断删除数字。

首先如果是 >，那么就只能删除最大值，有一种选法。

其次如果是 <，那么只能删除最小值，也只有一种选法。

当操作为 ? 时，那么既不删除最大值，也不删除最小值，有 len - 2 种选法，len 是数组长度。

因为当第 i 次操作完的时候有 i 个数字，去除最大最小值，答案就是所有满足 s_i = ? 的 (i - 2) 的乘积。

对于每一个询问，如果要将是问号的一位改成别的（s_i = '?' \rightarrow s_i = >/<），那么就要除以 (i - 2)，这个可以使用逆元实现，不会的可以去补一补数论。当然，如果是一个别的字符改成问号也要记得乘上 (i - 2)。

还要特判，如果在只有两个数字的时候有 ?，那不可能完成！因为除了最大值就是最小值，所以要直接输出 0。

代码

/*******************************
| Author:  SunnyYuan
| Problem: D. Monocarp and the Set
| Contest: Codeforces - Educational Codeforces Round 156 (Rated for Div. 2)
| URL:     https://codeforces.com/contest/1886/problem/D
| When:    2023-10-11 14:41:49
| 
| Memory:  256 MB
| Time:    2000 ms
*******************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 300010, mod = 998244353;

int n, m, ans;
int modfs[N];
char s[N];

int pow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> (s + 2);
    for (int i = 1; i <= n; i++) modfs[i] = pow(i, mod - 2);
    ans = 1;
    for (int i = 3; i <= n; i++)
        if (s[i] == '?')
            ans = 1ll * ans * (i - 2) % mod;

    if (s[2] == '?') cout << "0\n";
    else cout << ans << '\n';

    int p;
    char x;
    while (m--) {
        cin >> p >> x;
        p++;
        if (s[p] == '?' && p > 2) ans = 1ll * ans * modfs[p - 2] % mod;
        if (x == '?' && p > 2) ans = 1ll * ans * (p - 2) % mod;
        s[p] = x;
        if (s[2] == '?') cout << "0\n";
        else cout << ans << '\n'; 
    } 
    return 0;
}