Skip to content

Lucas 定理

2021-08-23

INFO

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

简介

Lucas 定理用于求解大组合数对质数 pp106)取模:

(nm)(nmodpmmodp)(n/pm/p)(modp)

证明

我不想证。

解法

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

(nm)=n!m!(nm)!n!(m!)1[(nm)!]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/pm/p)(modp)

其中 (nmodpmmodp) 可以直接算,(n/pm/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[i1]imodp
  • inv[i]=(i!)1,参考 线性求逆元

    i1=(pi(pmodi)1)modpinv[i]=inv[i1]i1modp
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+logpn)

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