[模板]组合数

$ C_n^m = \frac{n!} {m! (n - m)! } $

预处理 $ n! $

1
2
fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;

线性计算 $ n! $ 的逆元

$ {m!} ^ {-1} = {(m + 1)!} ^ {-1} * (m + 1) $

1
2
facinv[n] = inverse(fac[n]);
    for (int i = n - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % MOD;

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
ll qpow(ll a, int n, ll mod) {
    ll res = 1;
    for (; n; n >>= 1, a = a * a % mod)
        if (n & 1) res = res * a % mod;
    return res;
}

ll inverse(ll a) { return qpow(a, MOD - 2, MOD); }

void combi_init() {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    facinv[n] = inverse(fac[n]);
    for (int i = n - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % MOD;
}

ll combi(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}