深入理解卢卡斯定理：如何高效计算大数组合数取模 (nCr % p)

在算法和 competitive programming（竞技编程）的世界里，计算组合数 $C(n, r)$ 对素数 $p$ 取模是一个非常经典但有时却让人头疼的问题。比如，给定 $n = 1000$, $r = 900$, $p = 13$，我们要计算 $C(1000, 900) \% 13$。如果你尝试先算出 $C(1000, 900)$ 这个巨大的天文数字再取模，普通的 64 位整数甚至高精度库都会面临严重的溢出风险或性能瓶颈。

在之前的文章中，我们讨论了基于动态规划（DP）的解法，虽然它解决了溢出问题，但当 $n$ 达到 $10^9$ 这样的大规模时，$O(n \times r)$ 的时间复杂度依然太慢了。今天，我们将一起深入探讨一种基于卢卡斯定理的更优雅、更高效的解决方案。它的时间复杂度仅为 $O(p^2 \times \log_p n)$，这让处理 $n$ 极大而 $p$ 相对较小的情况变得轻而易举。

问题的核心：为什么我们需要卢卡斯定理？

在正式介绍定理之前，让我们先理解一下动态规划方法的局限性。

通常，计算 $nCr \% p$ 的最直观方法是利用帕斯卡三角形的性质，通过公式 $nCr = (n-1)Cr + (n-1)C(r-1)$ 逐行构建数组。这种方法的空间复杂度可以优化到 $O(r)$，但时间复杂度仍然是线性的 $O(n \times r)$。

试想一下这个场景：

如果题目给出的 $n = 10^{18}$，而 $p$ 只是一个很小的素数，比如 17。此时 DP 方法需要构建一个巨大的数组，这完全是不可行的。

这就是我们需要卢卡斯定理的地方。它利用模运算的周期性，将原本巨大的 $n$ 和 $r$ 问题，“降维”成一系列只涉及 $0$ 到 $p-1$ 之间的小数字问题。

卢卡斯定理深入浅出

卢卡斯定理的内容不仅数学上很美，而且实现起来也非常直观。简单来说，它告诉我们：

> 当 $p$ 是素数时，$n$ 选 $r$ 的组合数模 $p$ 的结果，等于 $n$ 和 $r$ 在 $p$ 进制下各位数字的组合数之积。

#### 数学公式

如果我们将 $n$ 和 $r$ 表示为 $p$ 进制数：

$$ n = nk p^k + n{k-1} p^{k-1} + … + n1 p + n0 $$

$$ r = rk p^k + r{k-1} p^{k-1} + … + r1 p + r0 $$

其中 $ni$ 和 $ri$ 是 $p$ 进制下的第 $i$ 位数字（$0 \le ni, ri < p$），那么：

$$ \binom{n}{r} \equiv \prod{i=0}^{k} \binom{ni}{r_i} \pmod{p} $$

#### 直观理解

这就好比我们在十进制下处理大数。计算大数的乘法时，我们会拆解每一位分别计算，最后组合结果。卢卡斯定理也是一样，它将大组合数 $C(n, r)$ 的计算，拆解为 $k+1$ 个小组合数 $C(n0, r0), C(n1, r1), …$ 的计算。因为 $ni$ 和 $ri$ 都小于 $p$，这些小组合数可以用我们之前提到的 DP 方法快速算出（时间复杂度只有 $O(p^2)$），这比直接计算大 $n$ 要快得多。

算法实现步骤

基于上述理论，我们可以设计出算法的核心步骤：

• 进制分解：使用“除 $p$ 取余法”，不断计算 $n \% p$ 和 $r \% p$，得到当前最低位数字 $ni$ 和 $ri$。然后将 $n$ 和 $r$ 除以 $p$（即右移一位），处理更高位。
• 计算小组合数：对于每一对 $(ni, ri)$，由于都小于 $p$，我们可以直接调用基于 $O(p)$ 空间优化的 DP 函数 nCrModpDP(ni, ri, p) 来计算结果。
• 合并结果：将所有位计算得到的组合数结果相乘，并对 $p$ 取模。

代码实现与详解

下面我们将提供完整的 C++ 和 Java 实现。请注意，为了提高代码的可读性和实用性，我在代码中加入了详细的中文注释，并处理了边界情况（比如 $r > n$）。

#### C++ 实现

在 C++ 中，我们可以利用 vector 或固定数组来实现 DP 部分。这里我们使用数组来展示最底层的逻辑。

// 基于 Lucas Theorem 计算 nCr % p 的 C++ 解法
#include
using namespace std;

// 辅助函数：返回 nCr % p。
// 注意：在这个基于 Lucas Theorem 的程序中，
// 该函数仅在 n < p 且 r 
 n，组合数为 0
    if (r > n) return 0;

    // 数组 C 将用于存储帕斯卡三角形的当前行。
    // 初始时代表第 0 行，只有 C[0] = 1。
    int C[r+1];
    memset(C, 0, sizeof(C));
    C[0] = 1; 

    // 从上到下逐行构建帕斯卡三角形（从第 1 行到第 n 行）
    for (int i = 1; i  0; j--) {
            // 组合数递推公式：nCj = (n-1)Cj + (n-1)C(j-1)
            // 我们在这里直接取模 p 以防止溢出
            C[j] = (C[j] + C[j-1]) % p;
        }
    }
    return C[r];
}

// 主函数：基于 Lucas Theorem 返回 nCr % p
// 该函数的工作原理类似于递归地将十进制转为 p 进制处理
int nCrModpLucas(int n, int r, int p) {
    // 基本情况：如果 r 为 0，根据定义 C(n, 0) = 1
    if (r == 0)
        return 1;

    // 步骤 1：计算 n 和 r 在 p 进制下的最后一位数字（当前位）
    int ni = n % p;
    int ri = r % p;

    // 步骤 2：递归计算剩余高位
    // 调用自身处理 n/p 和 r/p
    // 步骤 3：计算当前位的小组合数
    // 最后将两部分结果相乘并对 p 取模
    return (nCrModpLucas(n/p, r/p, p) * 
            nCrModpDP(ni, ri, p)) % p;
}

// 主程序用于测试
int main() {
    int n = 1000, r = 900, p = 13;
    cout << "Value of " << n << "C" << r << " % " << p << " is " << nCrModpLucas(n, r, p) << endl;
    return 0;
}

#### Java 实现

Java 的实现逻辑与 C++ 完全一致，但在处理数组初始化时语法稍有不同。这对于习惯 Java 开发的读者可能更友好。

// 基于 Lucas Theorem 计算 nCr % p 的 Java 解法

class GFG {
    // 返回 nCr % p。在这个基于 Lucas Theorem 的程序中，
    // 该函数仅在 n < p 且 r 
 n) return 0;

        // 数组 C 用于存储组合数，初始化为0
        int[] C = new int[r + 1];
        C[0] = 1; // 帕斯卡三角形的顶行，C(0,0) = 1

        // 逐行计算帕斯卡三角形
        for (int i = 1; i  0; j--) {
                // 递推公式取模
                C[j] = (C[j] + C[j - 1]) % p;
            }
        }
        return C[r];
    }

    // 基于 Lucas Theorem 返回 nCr % p 的递归函数
    static int nCrModpLucas(int n, int r, int p) {
        // 基本情况：C(n, 0) = 1
        if (r == 0)
            return 1;

        // 提取 p 进制下的当前最后一位数字
        int ni = n % p;
        int ri = r % p;

        // 递归调用处理高位，乘以当前位的 DP 结果
        return (nCrModpLucas(n / p, r / p, p) * 
                nCrModpDP(ni, ri, p)) % p;
    }

    // 主程序
    public static void main(String[] args) {
        int n = 1000, r = 900, p = 13;
        System.out.println("Value of " + n + "C" + r + " % " + p + " is " + nCrModpLucas(n, r, p));
    }
}

复杂度分析与实战建议

#### 时间复杂度

• nCrModpDP 函数：因为它运行在 $n < p$ 的范围内，循环次数最多 $p$ 次，内部循环最多 $p$ 次，所以复杂度是 $O(p^2)$。由于 $p$ 通常是固定的且较小（例如常用的质数 $10^9+7$ 除外，但 Lucas 常用于 $p$ 较小的情况），这部分很快。
• INLINECODEa6e0a986 函数：这是一个递归函数，递归的深度取决于 $n$ 在 $p$ 进制下的位数。位数大约是 $\logp n$。每次递归都会调用一次 INLINECODE51a74bdc。因此，总的时间复杂度为 $O(p^2 \times \logp n)$。

对比 DP 解法的 $O(n \times r)$，当 $n=10^6$ 或更大时，卢卡斯定理的优势是决定性的。

#### 常见陷阱与错误处理

• $p$ 必须是素数：卢卡斯定理严格依赖于 $p$ 是素数。如果 $p$ 是合数，该定理不直接适用。如果题目给出的 $p$ 是合数，你需要考虑中国剩余定理（CRT）或其他高级数论算法，或者使用费马小定理的扩展版本，这超出了本文的范围，但务必注意题目条件。
• $r > n$ 的情况：虽然在计算组合数时我们知道如果 $r > n$ 结果为 0，但在递归的子问题（INLINECODE4ddd1cde）中，也可能出现 $ri > ni$ 的情况（例如 $r$ 的某位数字大于 $n$ 的对应位数字）。此时 $C(ni, ri)$ 必须返回 0。我在上面的代码中已经加入了对 INLINECODE223792d8 的判断来处理这种情况。
• 递归深度：虽然递归深度只有 $\log_p n$（通常很小，几十到几百），但在极端严格的系统中可以考虑将其改写为迭代形式，但在绝大多数编程竞赛或工程实践中，递归是完全没问题的。

结语

通过这篇文章，我们一起攻克了计算大数组合数取模这一难题。我们不仅仅记住了卢卡斯定理的公式，更重要的是理解了它如何通过进制转换将复杂问题化简的思维方式。当你下次面对 $n$ 巨大而 $p$ 较小的取模问题时，不妨试试卢卡斯定理，它会让你的代码效率提升几个数量级。希望这些详细的解释和代码示例能帮助你在算法之路上更进一步！