当前位置：首页 > news >正文

扩展 Lucas 定理学习笔记详解，一文带你彻底看懂扩展 Lucas 定理。

news 2026/6/17 16:50:58

背景

考虑这样一个问题：

给定 \(n, r, p\) ，求

\[\binom{n}{r} \bmod m \]

不保证 \(m\) 是质数。\(1\le r\le n\le 10^{18}\)。

显然此时普通 Lucas 定理就无能为力了。这时需要用到扩展 Lucas 定理（exLucas）。

前置知识

你需要知道：

扩展欧几里得算法（exgcd）；
中国剩余定理（CRT）；
Legendre 公式；
关于“阶乘余数”的递归公式。

约定记号

\(v_p(n!)\) ：\(n!\) 中质因子 \(p\) 的次数；
\((n!)_p\) ：\(n!\) 去掉所有的 \(p\) 因子。

算法流程

我们将模数 \(m\) 分解质因数：\(m=p_1^{a_1}p_2^{a_2}\cdots p_{n}^{a_n}\) ；
我们构造方程组

\[\begin{cases} x \equiv r_1 \pmod{p_1^{a_1}} \\ x \equiv r_2 \pmod{p_2^{a_2}} \\ \cdots \cdots\\ x \equiv r_n \pmod{p_n^{a_n}} \end{cases} \]

注意到这些方程里的模数两两互质。我们使用 CRT 合并求解 \(x\) ，即为我们想要的答案 \(\binom{n}{r}\bmod m\) 。

接下来的问题就完全聚焦到了 \(r_i\) 的构造上来。我们考虑如下流程：

明确我们要构造 \(r_i\equiv \binom{n}{r}\pmod{p_i^{a_i}}\) ；
转化问题。我们需要求解 \(\binom{n}{r}\bmod p^a\) ，其中 \(p\) 是质数。即我们要求解如下式子：

\[\frac{n!}{n!(n-r)!}\bmod p^a \]

注意到分母 \(r!(n-r)!\) 与 \(p^a\) 不一定互质。那么就意味着我们没有办法求分母的逆元，进一步我们无法求解这个分式。考虑我们该如何改写它。
我们目标是使分母和 \(p^a\) 互质。为此我们将式子改写为：

\[p^v\frac{(n!)_p}{(r!)_p((n-r)!)_p} \bmod p^a \]

其中 \(v=v_p(n!)-v_p(r!)-v_p((n-r)!)\) 。注意到若 \(v\ge a\) ，则结果为 \(0\) 。

计算 \(v_p(n!)\) 。这可以利用 Legendre 公式求出：

\[v_p(n!) = \sum_{i=1}^{\infty}\left\lfloor \frac{n}{p^i} \right\rfloor \]

计算 \((n!)_p\) 。利用前置知识中提到的递归公式：

\[(n!)_p \equiv (\pm1)^{\lfloor n/p^a\rfloor}(\lfloor n/p \rfloor!)_p \left(\prod_{1\le j\le(n\bmod p^a)且j\nmid p}j\right) \pmod{p^a} \]

一些注意事项：

i. \((\lfloor n/p\rfloor!)_p\) 可以利用循环来展开递归，加快速度；

ii. \(\prod j\) 项，等价于在 \((n\bmod p^a)!\) 中去掉 \(p\) 因子，故这里可以直接预打表，用 f[i] 来表示 \(i!\) 中去掉 \(p\) 因子的值。这个表只用打到 \(i\le p^a\) 即可。

iii. 式子中 \(\pm 1\) 的取值：当且仅当 \(p=2\) 且 \(a\ge 3\) 时，\(\pm1\) 取正；否则取负。

于是我们完成了一个 \(r_i\) 的构造。按此流程，我们对每一个 \(p_i^{a_i}\) 构造一个 \(r_i\) ，就完成了方程组的构造。

复杂度分析

我们必须分解 \(m\) 。用试除法分解质因数的复杂度是 \(\mathcal O(\sqrt{m})\) 。
我们必须处理每个质因子。其中 Legendre 公式和递归公式的迭代次数都是 \(\mathcal O(\log_pn)\) 。

综上，这个算法的复杂度为 \(\mathcal O(\sqrt{m}+\sum\log_{p_i}n)\) 。

模板代码

这就是对上文思路的完全再现。如果还有不理解的过程，请参见下面的代码。

#include<iostream>
#include<vector>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define MIKU 0
using namespace std;int n, m, p;  //求解 C(n,m) mod p。//扩展欧几里得求逆元。
int exgcd(int a, int b, int &x, int &y) {if(b == 0) {x = 1; y = 0; return a;}int d = exgcd(b, a%b, y, x);y -= a / b * x;return d;
}int inv(int a, int m) {int x, y;exgcd(a, m, x, y);return (x % m + m) % m;
}//对每个质因数构造 r_i
struct BPP {int p, a, pa;  //p:模数  a:次数  pa:p^a。vector<int> f;  //预处理 f[i] ，表示 i! 去掉 p 因子。//构造函数，计算出 pa 和 f。BPP(int prime, int power) : p(prime), a(power) {pa = 1;for(int i=1; i<=a; i++) pa *= p;f.resize(pa); f[0] = 1;for(int i=1; i<pa; i++) f[i] = (i % p) ? f[i-1] * i % pa : f[i-1];}//利用 Legendre 公式求 vp(n!)int vp(int n, int cnt = 0) {for(; n; n/=p) cnt += n / p;return cnt;}//利用递归公式求 (n!)_p 。代码中用循环代替递归。int fac(int n, int res = 1) {bool neg = (p != 2 || a < 3);for(; n>1; n/=p) {if((n / pa) & neg) res = pa - res;  //这一步完成符号修正，即公式中第一个因子。res = res * f[n%pa] % pa;}return res;}//利用 vp(n!) 和 (n!)_p 算 C(n,r) mod p^a。 int C(int n, int r) {int v = vp(n) - vp(r) - vp(n-r);if(v >= a) return 0;int res = fac(n) * inv(fac(r) * fac(n-r) % pa, pa) % pa;for(; v; v--) res = res * p % pa;return res;}
};//扩展 Lucas ，负责完成质因数分解和 CRT 合并。
int exLucas(int n, int r, int m, int res = 0) {int tmp = m;for(int p=2; p*p<=tmp; p++) {  //试除法分解质因数。if(tmp % p) continue;int a = 0, pa = 1;for(; tmp%p==0; tmp/=p) a ++, pa *= p;BPP bpp = BPP(p, a);int ri = bpp.C(n, r);int mi = m / pa;res = (res + mi * ri % m * inv(mi, pa)) % m;  // CRT 合并公式。}if(tmp > 1) {BPP bpp = BPP(tmp, 1);int ri = bpp.C(n, r);int mi = m / tmp;res = (res + mi * ri % m * inv(mi, tmp)) % m;}return res;
}signed main() {fastio;cin>>n>>m>>p;cout<<exLucas(n, m, p);return 0;
}

例题

洛谷 P4720 【模板】扩展卢卡斯定理 / exLucas

这是一道模板题。代码见上面的模板代码。

洛谷 P2480 SDOI2010\ 古代猪文

这题其实并没有用到扩展 Lucas，但是它的思路和扩展 Lucas 是相通的。

详细题解戳 [这里]([Luogu P2480 SDOI2010] 古代猪文题解 - EtherealYz - 博客园) 。

洛谷 P2183 [国家集训队] 礼物

我们对 \(w_i\) 做前缀和，显然答案是 \(\sum_{i=1}^m\binom{n-s_{i-1}}{w_i}\) 。

容易注意到当 \(s_{m}>n\) 是无解。

主要难点是不保证模数为质数。这就需要用到扩展 Lucas 定理。

下面贴出代码。相比于上面的模板代码，只改动了主函数。

#include<iostream>
#include<vector>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define MIKU 0
using namespace std;int mod, n, m, ans = 1;
int w[10], s[10];int exgcd(int a, int b, int &x, int &y) {if(b == 0) {x = 1; y = 0; return a;}int d = exgcd(b, a%b, y, x);y -= a / b * x;return d;
}int inv(int a, int m) {int x, y;exgcd(a, m, x, y);return (x % m + m) % m;
}struct BPP {int p, a, pa;vector<int> f;BPP(int prime, int power) : p(prime), a(power) {pa = 1;for(int i=1; i<=a; i++) pa *= p;f.resize(pa); f[0] = 1;for(int i=1; i<pa; i++) f[i] = (i % p) ? f[i-1] * i % pa : f[i-1];}int vp(int n, int cnt = 0) {for(; n; n/=p) cnt += n / p;return cnt;}int fac(int n, int res = 1) {bool neg = (p != 2 || a < 3);for(; n>1; n/=p) {if((n / pa) & neg) res = pa - res;res = res * f[n%pa] % pa;}return res;}int C(int n, int r) {int v = vp(n) - vp(r) - vp(n-r);if(v >= a) return 0;int res = fac(n) * inv(fac(r) * fac(n-r) % pa, pa) % pa;for(; v; v--) res = res * p % pa;return res;}
};int exLucas(int n, int r, int m, int res = 0) {int tmp = m;for(int p=2; p*p<=tmp; p++) {if(tmp % p) continue;int a = 0, pa = 1;for(; tmp%p==0; tmp/=p) a ++, pa *= p;BPP bpp = BPP(p, a);int ri = bpp.C(n, r);int mi = m / pa;res = (res + mi * ri % m * inv(mi, pa)) % m;}if(tmp > 1) {BPP bpp = BPP(tmp, 1);int ri = bpp.C(n, r);int mi = m / tmp;res = (res + mi * ri % m * inv(mi, tmp)) % m;}return res;
}signed main() {fastio;cin>>mod>>n>>m;for(int i=1; i<=m; i++) cin>>w[i], s[i] = s[i-1] + w[i];if(s[m] > n) {cout<<"Impossible"; return MIKU;}for(int i=1; i<=m; i++) ans = ans * exLucas(n-s[i-1], w[i], mod) % mod;cout<<ans;return MIKU;
}