Lucas 定理NOIP

💡 核心思想

Lucas 定理用于计算大组合数 C(n,m) mod p，其中 p 为质数。定理内容：C(n,m) ≡ C(n mod p, m mod p) · C(n/p, m/p) (mod p)。它将大组合数递归分解为多个小组合数的乘积，每个小组合数可以用预处理的阶乘和逆元在 O(1) 时间内计算。

🎯 直觉理解

Lucas 定理处理"模质数 p 固定、但 n 和 m 很大"的组合数 $C(n,m)mod p$：直接算阶乘根本放不下。

定理内容：把 n、m 写成 p 进制，则 $C(n,m)$ 模 p 等于每个"位"分别算组合数再相乘——大问题拆成 p 进制各位的小问题，每一位的数字都小于 p，可以用小阶乘 + 逆元直接算。

适用前提：p 必须是小质数（阶乘表能开下，一般 $10^5$ 左右）；p 不质数时得用扩展 Lucas。先验证一个具体例子（比如 p=7 的小数据）理解拆分过程，再背模板。

📝 算法流程

1. 预处理 0 到 p-1 的阶乘 fac[] 和逆元 inv[]
2. Lucas(n, m, p)：
3. 如果 m == 0，返回 1
4. 返回 C(n%p, m%p, p) * Lucas(n/p, m/p, p) % p
5. 其中 C(n,m,p) = fac[n] * inv[m] % p * inv[n-m] % p

$$\binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod{p}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;

const int P = 1000007; // 质数模数
ll fac[P], inv[P];

ll qpow(ll a, ll n, ll mod) {
    ll res = 1; a %= mod;
    while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < P; i++) fac[i] = fac[i-1] * i % P;
    inv[P-1] = qpow(fac[P-1], P-2, P);
    for (int i = P-2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % P;
}

ll C(ll n, ll m) {
    if (m > n || m < 0) 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;
}

int main() {
    init();
    cout << lucas(1000, 300) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目