C题

C题
设计状态：
表示在第i次出牌,表示没出。
当第i位是2时：

是,表示前面为的个数，是，表示除了前面为的剩下的所有。

就是到第轮，没有把第i位换掉的概率，而前面的2是一定要被换掉的，否则不会到第i轮。

当第i位是3时：

统计答案的时候，次显然是的概率，因为最后一位怎么操作都是次。

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

const int maxn = 2e6+10;
const ll mod = 998244353;

ll F[maxn],Finv[maxn];

inline ll quick_pow(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=(res*x)%mod;
        x=(x*x)%mod,p>>=1;
    }
    return res;
}

inline ll inv(ll a){return quick_pow(a,mod - 2);}

void init(){
    F[0]=Finv[0]=1ll;
    for(int i=1;i<maxn;i++){
        F[i]=F[i-1]*1ll*i%mod;
        Finv[i]=Finv[i-1]*1ll*inv(i)%mod;
    }
}

ll C(ll n,ll m){
    if(m<0||m>n)return 0;
    return F[n]*1ll*Finv[n-m]%mod*Finv[m]%mod;
}

int sum[maxn],n;
char str[maxn];
ll dp[maxn][2];

int main(){
    init();
    scanf("%d",&n);
    scanf("%s",str+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if(str[i]=='2')sum[i]++;
    }
    dp[0][1]=1;
    for(int i=1;i<=n;i++){
        ll a=i-1-sum[i-1];
        ll b=n-sum[i-1];
        ll p=C(b-1,a)*inv(C(b,a))%mod;
        if(str[i]=='2'){
            dp[i][1]=dp[i-1][1]*(1-p)%mod;
            dp[i][0]=dp[i-1][1]*p%mod;
        }
        else dp[i][1]=dp[i-1][1];
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        ans=(ans+1ll*i*dp[i][0])%mod;
    }
    ans=(ans+1ll*n*dp[n-1][1])%mod;
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
}