牛客挑战赛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;

}


全部评论

相关推荐

联想 服务器(逻辑) 税前30
AI牛可乐:哎呀,华子你看起来有点小焦虑呢!别担心,每个决定都有它的利弊。TCL催得紧,说明他们很看重你呀!不过,毁约这种事情可得考虑清楚,毕竟每个企业都有自己的规矩。想不想听听小牛的看法呢?如果你愿意,可以点击我的头像,我们私信聊聊,帮你分析一下~(≧▽≦)
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客977679609号:感觉你会的东西还挺多的但简历一般都不这样写,建议只写一页,教育经历只留学校,导师单位啥的全去了,作品展示和自我评价都去了,科研成果写在所获荣誉里,项目保留,浓缩成一页。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务