牛客小白月赛14 -B （逆元求组合数）

佚名 6年前 (2019-05-12) 随笔 1711人围观抢沙发百度已收录

题目链接：https://ac.nowcoder.com/acm/contest/879/B

题意：题目意思就是求ΣC(n,i)pⁱ(MOD+1-p)^n-i (k<=i<=n)，这里n,i范围为1e5，要用到逆元求组合数。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

AC代码：

#include<cstdio>
using namespace std;
typedef long long LL;
const LL MOD =998244353;
const int maxn=100005;

LL n,k,p,ans;
LL inv[maxn],F[maxn],Finv[maxn];

void init(){
    inv[1]=1;
    for(int i=2;i<=100000;++i)
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    F[0]=Finv[0]=1;
    for(int i=1;i<=100000;++i){
        F[i]=F[i-1]*i%MOD;
        Finv[i]=Finv[i-1]*inv[i]%MOD;
    }
}

LL qpow(LL a,LL b){
    LL ret=1;
    while(b){
        if(b&1) ret=(ret*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ret;
}

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

int main(){
    init();
    scanf("%lld%lld%lld",&n,&k,&p);
    for(LL i=k;i<=n;++i){
        ans+=C(n,i)*qpow(p,i)%MOD*qpow(MOD+1-p,n-i)%MOD;
        ans%=MOD;
    }
    printf("%lld\n",ans);
    return 0;
}