Lucas 定理及其模版题题目

Lucas 定理是怎么来的？

Lucas 定理的最直观证明是通过生成函数（母函数）和二项式定理来推导的。

首先，根据二项式定理，我们知道组合数 $C_n^m$ 其实就是多项式 $(1+x)^n$ 展开后 $x^m$ 这一项的系数。

对于任意质数 $p$，考虑 $(1+x)^p \pmod p$ 的展开式：

$$(1+x)^p = C_p^0 x^0 + C_p^1 x^1 + C_p^2 x^2 + \dots + C_p^p x^p$$

因为 $p$ 是质数，当 $1 \le i \le p-1$ 时，$C_p^i = \frac{p!}{i!(p-i)!}$ 的分子里有一个 $p$，而分母里没有 $p$ 可以把它约掉。所以中间所有的项都是 $p$ 的倍数，在模 $p$ 意义下全部等于 $0$。
因此我们得到了一个非常漂亮的核心结论：

$$(1+x)^p \equiv 1 + x^p \pmod p$$

现在我们来求 $(1+x)^n \pmod p$ 中 $x^m$ 的系数。
我们将 $n$ 和 $m$ 拆分成除以 $p$ 的商和余数（类似于把它们转成 $p$ 进制）：
令 $n = \lfloor n/p \rfloor \times p + (n \bmod p)$
令 $m = \lfloor m/p \rfloor \times p + (m \bmod p)$

代入多项式中：

由于前面证明的核心结论，把内部的 $(1+x)^p$ 替换掉：

$$\begin{aligned}(1+x)^n &= (1+x)^{\lfloor n/p \rfloor \times p + (n \bmod p)} \\&= \left( (1+x)^p \right)^{\lfloor n/p \rfloor} \times (1+x)^{n \bmod p} \\\end{aligned}$$

$$\begin{aligned}(1+x)^n &\equiv (1+x^p)^{\lfloor n/p \rfloor} \times (1+x)^{n \bmod p} \pmod p\end{aligned}$$

我们要求的是 $x^m$ 的系数，而 $x^m = (x^p)^{\lfloor m/p \rfloor} \times x^{m \bmod p}$。
所以在右边这两个括号相乘时，我们必须：

1. 从前一个括号 $(1+x^p)^{\lfloor n/p \rfloor}$ 中选出 $(x^p)^{\lfloor m/p \rfloor}$，这部分的系数是 $C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}$。

2. 从后一个括号 $(1+x)^{n \bmod p}$ 中选出 $x^{m \bmod p}$，这部分的系数是 $C_{n \bmod p}^{m \bmod p}$。

两者相乘，就得到了 $x^m$ 的总系数。这就是 Lucas 定理的来源：

$$C_{n}^{m} \equiv C_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p$$

---

关于这道 AcWing 题目与你的模板

注意观察这道题目的输入格式：每一组询问都会给出一个不同的质数 $p$！

我们刚才在你的 main.tex 里，把 Lucas 定理改成了复用你已有的 Comb 命名空间和全局的 mod。那个模板只适用于所有询问的模数 $p$ 固定不变的情况（因为我们需要针对固定的 mod 预处理阶乘）。

对于这道题，因为 $p$ 会变（最高到 $10^5$），所以我们不能用全局预处理，反而应该用我们刚才撤掉的那份按定义暴力算的代码！因为暴力算单次是 $O(p)$ 的，加上 Lucas 递归，总时间大概是 $O(p \log_p n)$，这道题 $n \le 20$ 组询问，最大运算量在 $2 \times 10^6$ 左右，完全可以光速通过。

以下是可以直接通过这道题的 AC 代码，风格和我们刚才讨论的完全一致：

AC

https://www.acwing.com/problem/content/submission/code_detail/44735227/

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll mod;

// 你的组合数模板
namespace Comb{    
  vector<ll> frac, infrac;
  int ln = 1;
  bool initialized = false;

  inline ll binpow(ll a, ll k) {
    ll res = 1;
    a %= mod;
    while (k > 0) {
      if (k & 1) res = (res * a) % mod;
      a = (a * a) % mod;
      k >>= 1;
    }
    return res;
  }

  void Comb(int n) {
    ln = n;
    frac.assign(n + 5, 1);
    infrac.assign(n + 5, 1);
    for (int i = 1; i <= ln; ++i) {
      frac[i] = (frac[i - 1] * i) % mod;
    }
    infrac[ln] = binpow(frac[ln], mod - 2);
    for (int i = ln - 1; i >= 0; --i) {
      infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
    }
  }

  inline ll CC(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    if(!initialized){
      // 【核心细节】：Lucas定理的余数最大为 mod-1，所以只用预处理到 mod-1。
      // 绝对不能预处理到 mod，否则 frac[mod] = 0，会导致所有的 infrac 变成 0。
      Comb(mod - 1); 
      initialized = true;
    }
    ll res = frac[n];
    res = (res * infrac[n - k]) % mod;
    res = (res * infrac[k]) % mod;
    return res;
  }
}
using namespace Comb;

// Lucas 定理递归求解，复用 CC 模板
inline ll lucas(ll a, ll b) {
  if (a < mod && b < mod) return CC(a, b);
  return CC(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}

void solve() {
  ll a, b;
  cin >> a >> b >> mod;
  
  // 每次 mod 发生变化，必须重置初始化标记
  initialized = false; 
  
  cout << lucas(a, b) << '\n';
}

int main() {
  // 优化输入输出
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n;
  if (cin >> n) {
    while (n--) {
      solve();
    }
  }
  return 0;
}