競プロのライブラリ整理~逆元による二項係数の計算~

mod p(pは十分に大きいかつ素数)での二項係数を$O(n)$で前計算をして$O(1)$で求めるようにするライブラリを作成しました¹。

また、使用する際はこちらのテンプレートと一緒に使ってください。

また、前計算をする必要がない場合などの亜種もあり、詳しくはけんちょんさんの記事を参考にしてください。

combination.cc

vector<ll> fac,finv,inv;

//二項係数の前計算
//n:=二項係数xCyを求める時の最大のx
void COMinit(ll n) {
    fac.resize(n+1);
    finv.resize(n+1);
    inv.resize(n+1);
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,n){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

// 二項係数の演算
ll COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

1. 逆元の計算方法についてはけんちょんさんの記事を参考にしてください。 ↩