C题_牛客博客

C题
设计状态： $dp[i][0/1]$
$dp[i][0]$ 表示在第i次出牌, $dp[i][1]$ 表示没出。
当第i位是2时：

$dp[i][0]=dp[i-1][1]*p;$

$dp[i][1]=dp[i-1][1]*(1-p);$
$p=C(b-1,a)/C(b,a)$
$b$ 是 $i-1-k$ , $k$ 表示前面为 $2$ 的个数， $a$ 是 $n-k$ ，表示除了前面为 $2$ 的剩下的所有。

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

当第i位是3时：

$dp[i][1]=dp[i-1][1]$

统计答案的时候， $n$ 次显然是 $dp[n-1][1]$ 的概率，因为最后一位怎么操作都是 $n$ 次。

#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;
}