ZT Blog
algorithm

卢卡斯定理

卢卡斯定理（Lucas' Theorem）是组合数学中用于计算大组合数模素数的核心定理，其核心思想是将大组合数分解为小组合数的乘积。以下结合参考文献进行详细讲解：

定理内容

对于素数 pp 和非负整数 n,kn, k，有：

(nk)≡(⌊n/p⌋⌊k/p⌋)⋅(n mod pk mod p)(modp)\binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot \binom{n \bmod p}{k \bmod p} \pmod{p}

其中：

  • ⌊⋅⌋\lfloor \cdot \rfloor 表示向下取整；
  • n mod pn \bmod p 和 k mod pk \bmod p 是模 pp 的余数（范围在 [0,p−1][0, p-1]）。

证明思路

证明基于二项式展开和模运算性质：

  1. 二项式展开： 考虑 (1+x)n≡(1+x)p⌊n/p⌋⋅(1+x)n mod p(modp)(1+x)^n \equiv (1+x)^{p \lfloor n/p \rfloor} \cdot (1+x)^{n \bmod p} \pmod{p}。 由于 (1+x)p≡1+xp(modp)(1+x)^p \equiv 1+x^p \pmod{p}（费马小定理），右侧可化为 (1+xp)⌊n/p⌋⋅(1+x)n mod p(1+x^p)^{\lfloor n/p \rfloor} \cdot (1+x)^{n \bmod p}。

  2. 系数匹配： 左侧 xkx^k 的系数为 (nk)\binom{n}{k}，右侧需将 kk 分解为 k=p⌊k/p⌋+(k mod p)k = p \lfloor k/p \rfloor + (k \bmod p)。 此时 xkx^k 的系数为：

    (⌊n/p⌋⌊k/p⌋)⋅(n mod pk mod p)\binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot \binom{n \bmod p}{k \bmod p}

    等式成立。

  3. 边界处理：

    • 若 ⌊n/p⌋<⌊k/p⌋\lfloor n/p \rfloor < \lfloor k/p \rfloor，则 (nk)≡0(modp)\binom{n}{k} \equiv 0 \pmod{p}；
    • 若 k mod p>n mod pk \bmod p > n \bmod p，则 (n mod pk mod p)=0\binom{n \bmod p}{k \bmod p} = 0。

算法实现（C++ 代码）

#include <iostream>
using namespace std;

// 预处理阶乘及其逆元（用于小组合数计算）
const int MAX_P = 10000; // 假设 p < MAX_P
long long fact[MAX_P], inv_fact[MAX_P];

// 快速幂求逆元
long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 初始化阶乘表
void init(long long p) {
    fact = 1;
    for (int i = 1; i < p; i++) 
        fact[i] = fact[i - 1] * i % p;
    inv_fact[p - 1] = qpow(fact[p - 1], p - 2, p); // 费马小定理求逆元
    for (int i = p - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % p;
}

// 计算小组合数 C(n, k) mod p（要求 n, k < p）
long long C_small(long long n, long long k, long long p) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % p * inv_fact[n - k] % p;
}

// 卢卡斯定理递归计算
long long Lucas(long long n, long long k, long long p) {
    if (k == 0) return 1; // 递归终止条件
    long long n1 = n / p, k1 = k / p;        // 整除部分
    long long n2 = n % p, k2 = k % p;        // 余数部分
    if (k2 > n2) return 0;                   // 边界：余数组合数为0
    return C_small(n2, k2, p) * Lucas(n1, k1, p) % p;
}

int main() {
    long long n, k, p;
    cin >> n >> k >> p;
    init(p); // 预处理阶乘
    cout << Lucas(n, k, p) << endl;
    return 0;
}

关键点解析

  1. 递归分解： 将大组合数 (nk)\binom{n}{k} 递归分解为 (⌊n/p⌋⌊k/p⌋)\binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} 和 (n mod pk mod p)\binom{n \bmod p}{k \bmod p}，直到 n,k<pn, k < p。

  2. 预处理优化：

    • 预处理阶乘表 fact[] 及其逆元 inv_fact[]，使小组合数计算 O(1)O(1)；
    • 利用费马小定理求逆元（要求 pp 是素数）。

  3. 时间复杂度：

    • 递归深度 O(log⁡pn)O(\log_p n)，每层计算 O(1)O(1)；
    • 预处理 O(p)O(p)，总复杂度 O(p+log⁡pn)O(p + \log_p n)，适用于 pp 较小的情况。

  4. 与 exLucas 的关系： 当模数非素数时需用 exLucas 算法，但模数为素数时两者结果等价。

注意事项

  • 适用条件：仅当模数 pp 为素数时成立；
  • 边界处理：递归中需检查 k mod p≤n mod pk \bmod p \leq n \bmod p，否则组合数为 0。

此实现满足 OI/ACM 风格，兼顾效率与可读性。