快速组合数

通过预处理阶乘 + 逆元的方式快速计算$\left(\begin{array}{c}n\\ k\end{array}\right)$,在计算大组合数时候采用,在数字大于模数时候采用 Lucas 定理

Lucas 定理

对于质数$p$有组合数公式
$C(n,k)=\frac{n!}{k!(n-k)!}(\mathrm{mod}p)$
当$n<p$ 时候可以直接使用阶乘求:
$C(n,k)=fac[n]\cdot inv\_fac[k]\cdot inv\_[n-k]\mathrm{mod}p$
当$n\ge p$时候,Lucas定理告诉我们:
$C(n,k)\mathrm{mod}p=C\left(\lfloor \frac{n}{p}\rfloor ,\lfloor \frac{k}{p}\rfloor \right)\cdot C(n\mathrm{mod}p,k\mathrm{mod}p)\mathrm{mod}p$

下面给出板子:

ksm板子需自己补全

struct Comb
{
    vector<i64> fac, inv_fac;
    i64 MAX_N;
    Comb(i64 MAXK)
    {
        MAX_N = MAXK;
        fac.resize(MAX_N);
        inv_fac.resize(MAX_N);
        init();
    }
    // 预处理 [0, MOD-1] 阶乘及逆元
    void init()
    {
        fac[0] = 1;
        for (i64 i = 1; i < MAX_N; i++) fac[i] = fac[i - 1] * i % MOD;
        inv_fac[MAX_N - 1] = ksm(fac[MAX_N - 1], MOD - 2);
        for (i64 i = MAX_N - 2; i >= 0; i--) inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
    }
    // 计算 C(n, k) mod MOD，要求 n, k < MOD
    inline i64 C_small(i64 n, i64 k)
    {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
    }
    // Lucas 定理递归求解大组合数
    inline i64 C(i64 n, i64 k)
    {
        if (k < 0 || k > n) return 0;
        if (n < MOD && k < MOD) return C_small(n, k);
        return C(n / MOD, k / MOD) * C_small(n % MOD, k % MOD) % MOD;
    }
    inline i64 A(int n, int k) const
    {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv_fac[n - k];
    }
};