# 算法讲义：卢卡斯定理 (Lucas's Theorem)

## 1. 定理概述

**卢卡斯定理**用于处理大组合数取模问题。当组合数 $\binom{n}{k}$ 中的 $n, k$ 很大（例如 $10^{18}$），而模数 $p$ 是一个较小的**质数**（例如 $10^5$）时，利用常规的递推或阶乘公式无法直接计算，卢卡斯定理提供了有效的递归求解方法。

### 定理内容
对于质数 $p$，将 $n$ 和 $k$ 分别表示为 $p$ 进制数：
$n = n\_k p^k + n\_{k-1} p^{k-1} + \dots + n\_1 p + n\_0$
$k = m\_k p^k + m\_{k-1} p^{k-1} + \dots + m\_1 p + m\_0$

则有：
$$\binom{n}{k} \equiv \prod\_{i=0}^k \binom{n\_i}{m\_i} \pmod p$$

### 递归表达式（更常用）
$$\binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot \binom{n \bmod p}{k \bmod p} \pmod p$$

**边界条件**：
- 当 $k = 0$ 时，$\binom{n}{0} = 1$。
- 当 $n < k$ 时，$\binom{n}{k} = 0$。

---

## 2. 定理证明

我们需要利用二项式定理的一个引理：若 $p$ 为质数，则对于 $0 < i < p$，$\binom{p}{i}$ 是 $p$ 的倍数。
由此可得：
$$(1+x)^p \equiv 1 + x^p \pmod p$$

**证明步骤：**
考虑 $(1+x)^n \pmod p$ 的 $x^k$ 项系数：
1.  令 $n = qp + r$，其中 $r = n \bmod p, q = \lfloor n/p \rfloor$。
2.  $(1+x)^n = (1+x)^{qp} \cdot (1+x)^r$
3.  根据引理：$((1+x)^p)^q \cdot (1+x)^r \equiv (1+x^p)^q \cdot (1+x)^r \pmod p$
4.  展开两边：
    - 左边项中 $x^k$ 的系数为 $\binom{n}{k}$。
    - 右边 $(1+x^p)^q$ 展开后的项是 $x^{ip}$，$(1+x)^r$ 展开后的项是 $x^j$。
5.  设 $k = sp + t$（即 $s = \lfloor k/p \rfloor, t = k \bmod p$）。要得到 $x^k$，必须满足 $ip + j = sp + t$。由于 $j, t < p$，唯一解是 $i=s, j=t$。
6.  右边 $x^{sp} \cdot x^t$ 的系数为 $\binom{q}{s} \cdot \binom{r}{t}$。
7.  对比系数得：$\binom{n}{k} \equiv \binom{q}{s} \cdot \binom{r}{t} \pmod p$。

即：$\binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot \binom{n \bmod p}{k \bmod p} \pmod p$。证毕。

---

## 3. 应用举例

**题目：** 计算 $\binom{10}{3} \pmod 3$。

**解析：**
$n=10, k=3, p=3$。
1.  $\lfloor n/p \rfloor = 10/3 = 3$, $n \bmod p = 10 \bmod 3 = 1$。
2.  $\lfloor k/p \rfloor = 3/3 = 1$, $k \bmod p = 3 \bmod 3 = 0$。
3.  根据公式：$\binom{10}{3} \equiv \binom{3}{1} \cdot \binom{1}{0} \pmod 3$。
4.  继续递归 $\binom{3}{1}$：
    - $\binom{3}{1} \equiv \binom{1}{0} \cdot \binom{0}{1} \equiv 1 \cdot 0 = 0 \pmod 3$。（注：这里也可以直接通过 $3 \equiv 0 \pmod 3$ 得出）
5.  最终结果：$0 \cdot 1 = 0$。

**验证：** $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$。$120 \div 3 = 40 \dots 0$。正确。

---

## 4. 代码实现 (C++)

在实现卢卡斯定理前，需要先实现**费马小定理求逆元**的小组合数计算函数。

```cpp
#include <iostream>
using namespace std;

typedef long long ll;

// 快速幂计算 (a^        b) % p
ll power(ll a, ll b, ll p) {
    ll res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 费马小定理求逆元：inv(a) = a^(p-2) % p (p必须为质数)
ll modInverse(ll n, ll p) {
    return power(n, p - 2, p);
}

// 普通组合数计算 C(n, k) % p，n和k较小 (n < p)
ll C(ll n, ll k, ll p) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n / 2) k = n - k; // 优化

ll num = 1, den = 1;
    for (int i = 0; i < k; ++i) {
        num = num * (n - i) % p;
        den = den * (i + 1) % p;
    }
    return num * modInverse(den, p) % p;
}

// 卢卡斯定理核心递归
ll lucas(ll n, ll k, ll p) {
    if (k == 0) return 1;
    return (lucas(n / p, k / p, p) * C(n % p, k % p, p)) % p;
}

int main() {
    ll n, k, p;
    // 输入示例：n=10, k=3, p=3 -> 输出 0
    // 输入示例：n=1000, k=500, p=10007 -> 输出较大值取模结果
    while (cin >> n >> k >> p) {
        cout << lucas(n, k, p) << endl;
    }
    return 0;
}
```

---

## 5. 复杂度与限制

-   **时间复杂度**：$O(p + \log\_p n)$。
    -   如果预处理 $p$ 以内的阶乘，单次查询可优化至 $O(\log\_p n)$。
    -   如果不预处理，单次计算 $C(n \bmod p, k \bmod p)$ 需要 $O(p)$ 或 $O(k \bmod p)$。
-   **空间复杂度**：$O(1)$ 或 $O(p)$（取决于是否预处理阶乘）。
-   **局限性**：
    1.  模数 $p$ 必须是**质数**。如果 $p$ 是合数，需要使用**扩展卢卡斯定理 (Extended Lucas)**。
    2.  当 $p$ 过大（如 $p > 10^7$）且需要频繁计算时，预处理阶乘的空间开销较大。

---

## 6. 总结

卢卡斯定理是解决**大组合数、小质数取模**问题的利器。其核心思想是将 $n, k$ 进行 $p$ 进制拆分，将大规模问题转化为若干个 $p$ 范围内的小规模组合数乘积。在信息学竞赛（OI/ACM）中，它是数论部分的常考知识点。

算法讲义：卢卡斯定理 (Lucas's Theorem)

1. 定理概述

卢卡斯定理用于处理大组合数取模问题。当组合数 $\binom{n}{k}$ 中的 $n, k$ 很大（例如 $10^{18}$），而模数 $p$ 是一个较小的质数（例如 $10^5$）时，利用常规的递推或阶乘公式无法直接计算，卢卡斯定理提供了有效的递归求解方法。

定理内容

对于质数 $p$，将 $n$ 和 $k$ 分别表示为 $p$ 进制数： $n = n_k p^k + n_{k-1} p^{k-1} + \dots + n_1 p + n_0$ $k = m_k p^k + m_{k-1} p^{k-1} + \dots + m_1 p + m_0$

则有： $$\binom{n}{k} \equiv \prod_{i=0}^k \binom{n_i}{m_i} \pmod p$$

递归表达式（更常用）

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

边界条件： - 当 $k = 0$ 时，$\binom{n}{0} = 1$。 - 当 $n < k$ 时，$\binom{n}{k} = 0$。

2. 定理证明

我们需要利用二项式定理的一个引理：若 $p$ 为质数，则对于 $0 < i < p$，$\binom{p}{i}$ 是 $p$ 的倍数。由此可得： $$(1+x)^p \equiv 1 + x^p \pmod p$$

证明步骤： 考虑 $(1+x)^n \pmod p$ 的 $x^k$ 项系数： 1. 令 $n = qp + r$，其中 $r = n \bmod p, q = \lfloor n/p \rfloor$。 2. $(1+x)^n = (1+x)^{qp} \cdot (1+x)^r$ 3. 根据引理：$((1+x)^p)^q \cdot (1+x)^r \equiv (1+x^p)^q \cdot (1+x)^r \pmod p$ 4. 展开两边： - 左边项中 $x^k$ 的系数为 $\binom{n}{k}$。 - 右边 $(1+x^p)^q$ 展开后的项是 $x^{ip}$，$(1+x)^r$ 展开后的项是 $x^j$。 5. 设 $k = sp + t$（即 $s = \lfloor k/p \rfloor, t = k \bmod p$）。要得到 $x^k$，必须满足 $ip + j = sp + t$。由于 $j, t < p$，唯一解是 $i=s, j=t$。 6. 右边 $x^{sp} \cdot x^t$ 的系数为 $\binom{q}{s} \cdot \binom{r}{t}$。 7. 对比系数得：$\binom{n}{k} \equiv \binom{q}{s} \cdot \binom{r}{t} \pmod p$。

即：$\binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot \binom{n \bmod p}{k \bmod p} \pmod p$。证毕。

3. 应用举例

题目： 计算 $\binom{10}{3} \pmod 3$。

解析： $n=10, k=3, p=3$。 1. $\lfloor n/p \rfloor = 10/3 = 3$, $n \bmod p = 10 \bmod 3 = 1$。 2. $\lfloor k/p \rfloor = 3/3 = 1$, $k \bmod p = 3 \bmod 3 = 0$。 3. 根据公式：$\binom{10}{3} \equiv \binom{3}{1} \cdot \binom{1}{0} \pmod 3$。 4. 继续递归 $\binom{3}{1}$： - $\binom{3}{1} \equiv \binom{1}{0} \cdot \binom{0}{1} \equiv 1 \cdot 0 = 0 \pmod 3$。（注：这里也可以直接通过 $3 \equiv 0 \pmod 3$ 得出） 5. 最终结果：$0 \cdot 1 = 0$。

验证： $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$。$120 \div 3 = 40 \dots 0$。正确。

4. 代码实现 (C++)

在实现卢卡斯定理前，需要先实现费马小定理求逆元的小组合数计算函数。

#include <iostream>
using namespace std;

typedef long long ll;

// 快速幂计算 (a^        b) % p
ll power(ll a, ll b, ll p) {
    ll res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 费马小定理求逆元：inv(a) = a^(p-2) % p (p必须为质数)
ll modInverse(ll n, ll p) {
    return power(n, p - 2, p);
}

// 普通组合数计算 C(n, k) % p，n和k较小 (n < p)
ll C(ll n, ll k, ll p) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n / 2) k = n - k; // 优化

    ll num = 1, den = 1;
    for (int i = 0; i < k; ++i) {
        num = num * (n - i) % p;
        den = den * (i + 1) % p;
    }
    return num * modInverse(den, p) % p;
}

// 卢卡斯定理核心递归
ll lucas(ll n, ll k, ll p) {
    if (k == 0) return 1;
    return (lucas(n / p, k / p, p) * C(n % p, k % p, p)) % p;
}

int main() {
    ll n, k, p;
    // 输入示例：n=10, k=3, p=3 -> 输出 0
    // 输入示例：n=1000, k=500, p=10007 -> 输出较大值取模结果
    while (cin >> n >> k >> p) {
        cout << lucas(n, k, p) << endl;
    }
    return 0;
}

5. 复杂度与限制

时间复杂度：$O(p + \log_p n)$。
- 如果预处理 $p$ 以内的阶乘，单次查询可优化至 $O(\log_p n)$。
- 如果不预处理，单次计算 $C(n \bmod p, k \bmod p)$ 需要 $O(p)$ 或 $O(k \bmod p)$。
空间复杂度：$O(1)$ 或 $O(p)$（取决于是否预处理阶乘）。
局限性：
1. 模数 $p$ 必须是质数。如果 $p$ 是合数，需要使用扩展卢卡斯定理 (Extended Lucas)。
2. 当 $p$ 过大（如 $p > 10^7$）且需要频繁计算时，预处理阶乘的空间开销较大。

6. 总结

卢卡斯定理是解决大组合数、小质数取模问题的利器。其核心思想是将 $n, k$ 进行 $p$ 进制拆分，将大规模问题转化为若干个 $p$ 范围内的小规模组合数乘积。在信息学竞赛（OI/ACM）中，它是数论部分的常考知识点。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com