题解：CF1886D Monocarp and the Set

xieqx0709 · 2025-12-02 16:50:16 · 题解

题意

给你一个长度为 n-1 的字符串 s，求长度为 n 的排列 a 个数，第 i 个字符表示 a_{i+1} 被放入一个集合的情况。

• 如果当前加入的元素成为集合中的最大值，s_i 为 >；
• 如果当前加入的元素成为集合中的最小值，s_i 为 <；
• 如果都不是，s_i 为 ?。

有 m 次询问，求把 s_x 改为 c 时 a 的个数。

思路

如果 s_1 为 ?，答案显然为 0，因为第二个数一定是最小值和最大值中的一个。

我们可以遍历 s，设当前遍历至 s_i。当 s_i 为 > 或 < 时，a_{i+1} 是固定的，故只有一种情况；当 s_i 为 ? 时，a_{i+1} 就有 i-1 种情况。

询问时除去这一位原有的贡献，再乘上修改后的贡献即可。

简单题，建议降黄。

代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define gc getchar
#define is isdigit
using namespace std;
inline int rd(){int f=1,p=0;char c=gc();
while(!is(c)&&c!=45)c=gc();if(c==45)f=-1,c=gc();
while(is(c))p=p*10+(c^48),c=gc();return f*p;}
const int mod=998244353;
int n,m,ans;
char s[300005];
inline int ksm(int a,int b,int s=1)//即快速幂
{
    while(b)
    {
        if(b&1)s=s*a%mod;
        a=a*a%mod,b>>=1;
    }
    return s;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    n=rd(),m=rd(),ans=1;//初始答案为1
    for(int i=1;i<n;i++)
        s[i]=gc();
    for(int i=2;i<n;i++)
        if(s[i]=='?')ans=ans*(i-1)%mod;//求原字符串答案
    cout<<(s[1]=='?'?0:ans)<<endl;
    while(m--)
    {
        int x=rd();
        if(x!=1&&s[x]=='?')ans=ans*ksm(x-1,mod-2)%mod;//这里要求逆元
        s[x]=gc();
        if(x!=1&&s[x]=='?')ans=ans*(x-1)%mod;
        cout<<(s[1]=='?'?0:ans)<<endl;
    }
    return 0;
}