浅谈 Lucas 定理

Bc2_Ch1ckenPr1nce · 2026-05-19 21:02:55 · 算法·理论

说明

由于篇幅原因，大部分例题不放代码。

【组合数学】上一篇：浅谈排列组合。

Part 0：前置知识

组合数。

Part 1：卢卡斯定理是什么

在算法竞赛中，我们经常需要计算组合数 \binom nk 对一个质数 p 取模的值，即：

\binom nk \bmod p

按照三种常规方法均有局限性：

直接计算法：\binom nk = \frac{n!}{k!(n - k)!}，当 n 很大时（例如超过 10^8）阶乘将会难以计算并存储；
递推法：\binom nk = \binom {n - 1}{k - 1} + \binom {n - 1}k，时间复杂度 \mathcal{O}(nk)，这种方法仅支持小的 n, k；
预处理阶乘+逆元法：这种方法可以处理 n < p 的情况，但当 n \ge p 时，n! 中包含因子 p，导致 n! \bmod p = 0，无法求逆元。

但卢卡斯定理专门解决大组合数对小质数取模的问题。当 p 是质数时，n, k 可以远远大于 p。远超常规预处理范围。但是，卢卡斯定理的核心思想就是将大组合数分解为多个小组合数的乘积，每个小组合数都满足 n_i < p，从而可以预处理。

Part 2：卢卡斯定理的公式

2.1：数学常用写法

设 p 是质数，将非负整数 n, k 表示为 p 进制数：

\begin{cases} n = n_mp^m + n_{m - 1}p^{m - 1} + \cdots + n_1p + n_0 \\ k = k_mp^m + k_{m - 1}p^{m - 1} + \cdots + k_1p + k_0\end{cases}

其中 0 \le n_i, k_i < p。

则有：

\binom nk \equiv \prod_{i = 0}^m \binom {n_i}{k_i} \pmod p

特别地，当 k_i > n_i 时，\binom {n_i}{k_i} = 0。

2.2：竞赛常用写法

在竞赛中，我们常使用递归形式：

\text{Lucas}(n, k, p) = \begin{cases} 1 & k = 0 \\ \binom {n \bmod p}{k \bmod p} \cdot \text{Lucas}(\frac{n}{p}, \frac{k}{p}, p) & \text{otherwise} \end{cases}

Part 3：卢卡斯定理的证明

3.1：关键引理

若 p 是质数，则对于任意整数 1 \le k \le p - 1，有：

\binom pk \equiv 0 \pmod p

证明：

展开组合数，得：

\binom pk = \frac{p!}{k!(p - k)!} = \frac{p \times (p - 1) \times \cdots \times (p - k + 1)}{k!}

\because 1 \le k \le p - 1

\therefore p \nmid k!

又 p \mid [p \times (p - 1) \times \cdots \times (p - k + 1)]

\therefore p \mid \binom pk

\therefore \binom pk \equiv 0 \pmod p

3.2：二项式展开的模性质

对于任意整数 a, b，都有：

(a + b)^p \equiv a^p + b^p \pmod p

证明：

根据二项式定理：

(a + b)^p = \sum_{k = 0}^p \binom pk a^{p - k}b^k

那么：

(a + b)^p \equiv a^p + b^p + \sum_{k = 1}^{p - 1}\binom pk a^{p - k}b^k \pmod p

根据引理，当 1 \le k \le p - 1 时，\binom pk \equiv 0 \pmod p。

所以：

(a + b)^p \equiv a^p + b^p \pmod p

3.3：推广形式

对于任意非负整数 m，都有：

(a + b)^{p^m} \equiv a^{p^m} + b^{p^m} \pmod p

证明：

使用数学归纳法。

当 m = 0 时，(a + b)^1 = a^1 + b^1，成立。

假设当 m = t 时成立，即：

(a + b)^{p^t} \equiv a^{p^t} + b^{p^t} \pmod p

那么，当 m = t + 1 时：

(a + b)^{p^{t + 1}} = \left[(a + b)^{p^t}\right]^p \equiv \left(a^{p^t} + b^{p^t}\right)^p \equiv (a^{p^t})^p + (b^{p^t})^p = a^{p^{t + 1}} + b^{p^{t + 1}}

成立。

3.4：卢卡斯定理的证明

将 n 和 k 表示为 p 进制数：

n = \sum_{i = 0}^m n_ip^i,\ k = \sum_{i = 0}^m k_ip^i

考虑二项式展开 (1 + x)^n \bmod p：

(1 + x)^n = (1 + x)^{\sum_{i = 0}^m n_ip^i} = \prod_{i = 0}^m \left[(1 + x)^{p^i}\right]^{n_i}

根据推论：

\prod_{i = 0}^m \left[(1 + x)^{p^i}\right]^{n_i} \equiv (1 + x^{p^i})^{n_i} \pmod p

所以：

(1 + x)^n \equiv \prod_{i = 0}^m (1 + x^{p^i})^{n_i} \pmod p

比较等式两边 x^k 的系数：

左边：根据二项式定理，x^k 的系数为 \binom nk；
右边：从每一个因子 (1 + x^{p^i})^{n_i} 中选择 x^{k_ip^i} 项，而这一项的系数为 \binom {n_i}{k_i}。因为 k = \displaystyle\sum_{i = 0}^mk_ip^i，所以 x^k 的系数为 \displaystyle \prod_{i = 0}^m \binom {n_i}{k_i}。

由于等式两边 x^k 的系数在模 p 的情况下相等，所以：

\binom nk \equiv \prod_{i = 0}^m \binom {n_i}{k_i} \pmod p

证毕。

Part 4：代码实现

预处理阶乘（也可以有逆元）；
写好组合数计算函数；
将 n 和 k 不断除以 p，然后递归实现 Lucas 函数；
记得特判 n < k 和 k = 0 的情况。

可以先自己尝试写，然后再参考示例代码。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 2e5 + 20;

ll n, m, p, fac[kMaxN];

ll Qpow(ll a, ll b, ll p) {
  ll ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      ans = ans * a % p;
    }
    a = a * a % p;
  }
  return ans;
}

ll C(ll n, ll m, ll p) {
  if (n < m) {
    return 0;
  }
  return fac[n] * Qpow(fac[m], p - 2, p) % p * Qpow(fac[n - m], p - 2, p) % p;
}

ll Lucas(ll n, ll m, ll p) {
  if (n < m) {
    return 0;
  } else if (!n) {
    return 1;
  }
  return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

void Init() {
  fac[0] = 1;
  for (int i = 1; i < kMaxN; ++ i) {
    fac[i] = fac[i - 1] * i % p;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n >> m >> p, Init();
    cout << Lucas(n + m, n, p) << '\n';
  }
  return 0;
}

::::

Part 5：例题

P2606 [ZJOI2010] 排列计数

题目中的条件完全二叉树小根堆性质，问题转化为统计合法小根堆构造方案数。

定义 f_i 为以节点 i 为根的子树合法方案数，s_i 为子树节点总数。

小根堆根节点必为子树最小值，剩余 s_i - 1 个数分配给左右子树，选取组合数搭配子树方案，得到转移式：

f_i = \binom{s_i - 1}{s_{2i}} \cdot f_{2i} \cdot f_{2i + 1}

从叶子向上递推计算，空树边界 f_i = 1\ (i>n)。最终答案为 f_1。

组合数需结合卢卡斯定理计算。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 3e6 + 10;

ll n, p, fac[kMaxN], f[kMaxN], sz[kMaxN], ans;

ll Qpow(ll a, ll b, ll p) {
  ll ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      ans = ans * a % p;
    }
    a = a * a % p;
  }
  return ans;
}

ll C(ll n, ll m, ll p) {
  if (n < m) {
    return 1;
  }
  return fac[n] * Qpow(fac[m], p - 2, p) % p * Qpow(fac[n - m], p - 2, p) % p;
}

ll Lucas(ll n, ll m, ll p) {
  if (n < m) {
    return 1;
  } else if (!n) {
    return 1;
  }
  return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

void Init() {
  fac[0] = 1;
  for (int i = 1; i < kMaxN; ++ i) {
    fac[i] = fac[i - 1] * i % p;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> p, Init();
  fill(sz + 1, sz + n + 1, 1), fill(f + n + 1, f + (n << 1) + 2, 1);
  for (int i = n; i >= 2; -- i) {
    sz[i >> 1] += sz[i];
  }
  for (int i = n; i; -- i) {
    f[i] = Lucas(sz[i] - 1, sz[i << 1], p) * f[i << 1] % p * f[(i << 1) | 1] % p;

  }
  cout << f[1] << '\n';
  return 0;
}

::::

P7976 「Stoi2033」园游会

先转化函数：

F(x) = \begin{cases}0 & x \bmod 3 = 0 \\ 1 & x \bmod 3 = 1 \\ -1 & x \bmod 3 = 2 \end{cases}

简单来说，就是把每个组合数对 3 取模后，映射成 0, 1, -1 再求和。

数据范围很大，无法直接计算组合数，因此使用卢卡斯定理处理模 3 组合数。

Lucas 定理表明：将 n, m 拆成三进制，有

\binom{n}{m} \equiv \prod \binom{n_i}{m_i} \pmod 3

若存在某一位 m_i > n_i，则 \binom{n}{m} \equiv 0 \pmod 3，该项贡献为 0。

逐位分析三进制每一位的总贡献：

当 n_i = 0 时，m_i 只能取 0，总贡献为 1。
当 n_i = 1 时，m_i 可取 0, 1，两种情况贡献均为 1，总贡献为 2。
当 n_i = 2 时，m_i 可取 0, 1, 2，对应贡献为 1, -1, 1，总贡献为 1。

可以发现，仅当三进制位 n_i = 2 且 m_i = 1 时会产生负贡献。

设这样的位数为 r，可以推出：

F\left(\binom{n}{m}\right) = (-1)^r

由于三进制每一位独立，答案就是所有位贡献相乘：遍历 n 的三进制每一位，遇 0, 2 乘 1，遇 1 乘 2，最终乘积即为答案。