Questions

Monocarp 有 \(n\) 个整数和一个集合，他需要把这 \(n\) 个数添加到集合中，每次添加一次

除了第一次，每次添加元素都会输出一个字符

• 如果当前添加的元素比原有的元素都要小，那么输出 \(>\)

• 如果当前添加的元素比原有的元素都要大，那么输出 \(<\)

• 否则输出 \(?\)

你给予了输出的字符串 \(s\) 有 \(m\) 组询问

• \(i\) \(c\) 表示用 \(c\) 替换 \(s_i\) 的值

在每次询问前和最后一个询问后，你都需要计算添加整数的方案数，对 998244353取模

Solution

先考虑不修改的情况，正过来做我们发现很难处理，就考虑反过来做

反过来就是对长度为 \(n\) 的数组一个一个删数字

• > 代表删除最大的数字
• < 代表删除最小的数字
• ?代表随意删除一个数字

为了方便我们理解，我们重新规定 \(S_i\) 表示数组元素个数为 \(i\) 时从数组中删除一个元素，这就需要我们在 \(S\) 前加上几个元素

所以很显然，当 < 和 > 时，方案数是 \(1\) ，当是 ? 时，方案数就是 \(i-2\)

所以对于一个的答案，我们就从后往前处理累积到 ans 上面就好了

对于 \(S_2=?\) 情况，显然方案数就是 \(0\) 因为两个肯定有大有小

那么对于询问的情况，那么就用除法和乘法来实现

如果是 ? 替换 < 的话，就需要把 \(ans/=(i-2)\)

由于考虑到要取模，我们需要乘上 \((i-2)\) 的逆元

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL TT=998244353;
const int maxn=2e5+5;

inline LL read(){
    LL ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

LL N,M,ans=1;
string s;

LL qpow(LL a,LL b){//快速幂求逆元
    LL ret=1;
    while(b){
        if(b&1)ret=ret*a%TT;
        a=a*a%TT;
        b>>=1;
    }
    return ret;
}
int main(){
    // freopen("D.in","r",stdin);
    // freopen("D.out","w",stdout);
    N=read();M=read();
    cin>>s;
    s="  "+s;
    for(int i=N;i>=3;i--)
        if(s[i]=='?') ans=ans*(i-2)%TT;
    printf("%lld\n",s[2]=='?'?0:ans);
    while(M--){
        LL pos=read()+1;
        char ch=getchar();
        if(pos>=3&&s[pos]=='?')
            ans=ans*qpow(pos-2,TT-2)%TT;
        s[pos]=ch;
        if(pos>=3&&s[pos]=='?')
            ans=ans*(pos-2)%TT;
        printf("%lld\n",s[2]=='?'?0:ans);
    }
    return 0;
}