Lucas 定理CSP-S

💡 核心思想

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) 时间内计算。

🎯 直觉理解

想象你要从 1000 个球中选 300 个，模数是 7。Lucas 定理说：你不需要直接算 C(1000,300)，而是把 1000 和 300 按 7 进制拆分：1000 = 2026₇，300 = 606₇。然后逐位相乘：C(2,6)=0... 等等，如果某一位 m mod p > n mod p，结果就是 0。这就像按位独立计算，然后把结果乘起来。

📝 算法流程

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

⚠️ 常见坑点

📚 相关题目