求组合数

求组合数

ll fact[N], infact[N];

ll qmi(ll a, ll k) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = a * ans % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int iniv(int x) {
    return qmi(x, mod - 2);
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * iniv(i) % mod;
    }
}

ll C(ll n, ll m) {
    if (n < m) return 1;
    return fact[n] * infact[n - m] % mod * infact[m] % mod;
}