Yharim Area

Appearance

Lucas 定理

2021-08-23

INFO

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

简介 ​

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

(nm)≡(nmodpmmodp)⋅(⌊n/p⌋⌊m/p⌋)(modp)

证明 ​

我不想证。

解法 ​

对于 n,m≤106 的组合数 (nm)，可以直接代入 组合数 公式，并使用 乘法逆元 将除法转为乘法。

(nm)=n!m!(n−m)!≡n!⋅(m!)−1⋅[(n−m)!]−1(modp)
cpp
/* 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 定理。

(nm)≡(nmodpmmodp)⋅(⌊n/p⌋⌊m/p⌋)(modp)

其中 (nmodpmmodp) 可以直接算，(⌊n/p⌋⌊m/p⌋) 需要递归求解。

cpp
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!modp，线性递推：

    fac[i]=fac[i−1]⋅imodp

  • inv[i]=(i!)−1，参考 线性求逆元：

    i−1=(−⌊pi⌋⋅(pmodi)−1)modpinv[i]=inv[i−1]⋅i−1modp
WARNING

此处的 inv[i] 不是 i 的逆元，而是 i 的阶乘的逆元。

cpp
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+logp⁡n)。

cpp
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;
}