Lucas 定理

若无特殊说明，本章涉及的变量皆为正整数.

简介 #

Lucas 定理用于求解大组合数对质数 $p$（$p≤10^6$）取模：

$${n\choose m}≡{n \bmod p\choose m \bmod p}\cdot{\lfloor n/p\rfloor\choose\lfloor m/p\rfloor} \ (\bmod \ p)$$

证明 #

我不会，长大后再学习.

解法 #

对于 $n,m≤10^6$ 的组合数 ${n\choose m}$，可以直接代入公式，并使用乘法逆元将除法转为乘法.

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}≡n!\cdot(m!)^{-1}\cdot[(n-m)!]^{-1} \ (\bmod \ p)$$

/* fac[x]: x!
 * inv[x]: x! 关于模 p 的乘法逆元（注意有阶乘）
 * 以上需要预处理
 */
LL C(LL n, LL m) {
    if (n < m)
        return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}

对于更大的组合数，套用 Lucas 定理.

$${n\choose m}≡{n \bmod p\choose m \bmod p}\cdot{\lfloor n/p\rfloor\choose\lfloor m/p\rfloor} \ (\bmod \ p)$$

其中 ${n \bmod p\choose m \bmod p}$ 可以直接算，${\lfloor n/p\rfloor\choose\lfloor m/p\rfloor}$ 需要递归求解.

LL lucas(LL n, LL m) {
    if (m == 0)
        return 1;
    return C(n % P, m % P) * lucas(n / P, m / P) % P;
}

预处理 #

$fac[i]=i!\bmod p$，线性递推：

$$fac[i]=fac[i-1]\cdot i\bmod p$$
$inv[i]=(i!)^{-1}$，参考线性求逆元：

$$i^{-1}=(-\Big\lfloor\frac{p}{i}\Big\rfloor\cdot(p\bmod i)^{-1}) \bmod p$$

$$inv[i]=inv[i - 1]\cdot i^{-1}\bmod p$$

void init() {
    fac[0] = fac[1] = 1;
    for (LL i = 2; i <= P; i ++)
        fac[i] = fac[i - 1] * i % P;

    inv[0] = inv[1] = 1;
    for (LL i = 2; i <= P; i ++)
        inv[i] = (P - P / i) * inv[P % i] % P;
    for (LL i = 2; i <= P; i ++)
        inv[i] = inv[i - 1] * inv[i] % P;
}

模板 #

总时间复杂度：$O(p+\log_p{n})$.

typedef long long LL;
const int N = 1e6 + 1, P = 10007;
LL fac[N], inv[N];

void init() {
    fac[0] = fac[1] = 1;
    for (LL i = 2; i <= P; i ++)
        fac[i] = fac[i - 1] * i % P;

    inv[0] = inv[1] = 1;
    for (LL i = 2; i <= P; i ++)
        inv[i] = (P - P / i) * inv[P % i] % P;
    for (LL i = 2; i <= P; i ++)
        inv[i] = inv[i - 1] * inv[i] % P;
}

LL C(LL n, LL m) {
    if (n < m)
        return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}

LL lucas(LL n, LL m) {
    if (m == 0)
        return 1;
    return C(n % P, m % P) * lucas(n / P, m / P) % P;
}