牛客挑战赛41 C -欢乐斗地主 概率dp

题目链接：https://ac.nowcoder.com/acm/contest/6012/C
题目大意：

思路：

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

const int MOD=998244353;
const int MAXN=2002020;
int fac[MAXN+5],facinv[MAXN+5];

long long quickmul(int a,int b){
    long long ret=1;
    for(; b ; b >>=1 ,a =(long long) a * a % MOD)
        if((b & 1))
            ret=ret * a % MOD;
    return ret;
}
long long C(int n,int m){
    if(n<0||m<0||n<m)
        return 0;
    return (long long)fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;
}

void init(){
    fac[0]=1;
    for(int i=1;i<=MAXN;i++)
        fac[i]=(long long)fac[i-1]*i%MOD;
    facinv[MAXN]=quickmul(fac[MAXN],MOD-2);
    for(int i=MAXN;i>0;i--)
        facinv[i-1]=(long long)facinv[i]*(i)%MOD;
        //1/(i-1)!=i/(i)!
}

char s[1000005];
long long f[1000005][2];
int main(){

    init();
    long long n; scanf("%lld%s", &n, s+1);
    long long k=0;
    if(s[1]=='2'){
        printf("1\n");
        return 0;
    }
    f[1][0]=1;
    for(int i=2; i<=n; i++){
        if(s[i]=='2'){
            long long b=i-1-k;
            long long a=n-k;
            long long p=C(a-1, b)*quickmul(C(a, b), MOD-2)%MOD;
            f[i][0]=f[i-1][0]*(1-p+MOD)%MOD;
            f[i][1]=f[i-1][0]*p%MOD;
            k++;
        }
        else{
            f[i][0]=f[i-1][0];
        }
    }
    long long ans=0;
    for(long long i=2; i<=n; i++){
        ans=(ans+i*f[i][1]%MOD)%MOD;
    }
    ans=(ans+f[n][0]*n%MOD)%MOD;
    printf("%lld\n", ans);

    return 0;

}