逆元求组合数

说明

  • mod必须为素数

该方法使用求逆元的方式求组合数

使用方法

  1. getfac();打表
  2. ll ans = C(n, m);计算组合数C(n, m);

模版

const int fcnt=100005;
const ll mod=1000000007;
ll fac[fcnt];
void getfac()
{
    fac[0]=1;
    for (int i=1; i<fcnt; i++)
        fac[i]=fac[i-1]*i%mod;
}
ll quickpow(ll a, ll b) {
    if (b < 0) return 0;
    ll ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
ll inv(ll a) {
    return quickpow(a, mod - 2);
}
ll C(ll n,ll m)
{
    if (n<m)
        return 0;
    return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}

results matching ""

    No results matching ""