Lucas（卢卡斯）定理
- 2021 年 4 月 18 日
- 笔记
定义
若 \(p\) 为质数，且\(a\ge b\ge1\)，则有：
\[C_{a}^{b}\equiv C_{a/p}^{b/p}\cdot C_{a (mod\,p)}^{b(mod\,p)}
\]
\]
拆分a与b
按照 \(p\) 进制拆分 \(a\) 与 \(b\) ,设 \(a\) 与 \(b\) 是 \(k\) 位，不足用 \(0\) 补足。
\[\left\{\begin{aligned}
a&=a_0p^{0}+a_1p^{1}+\cdots+a_{k-1}p^{k-1}+a_kp^{k}\\
b&=b_0p^{0}+b_1p^{1}+\cdots+b_{k-1}p^{k-1}+b_kp^{k}
\end{aligned}\tag{1}
\right.
\]
a&=a_0p^{0}+a_1p^{1}+\cdots+a_{k-1}p^{k-1}+a_kp^{k}\\
b&=b_0p^{0}+b_1p^{1}+\cdots+b_{k-1}p^{k-1}+b_kp^{k}
\end{aligned}\tag{1}
\right.
\]
证明\((1+x)^{p}\equiv1+x^p\,mod\,p\)
根据二项式定理有：
\[\begin{aligned}
(1+x)^p&=C_p^0x^0+C_p^1x^1+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+C_p^px^p\\
&=1+C_p^1x+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+x^p\\
(1+x)^p&=C_p^0x^0+C_p^1x^1+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+C_p^px^p\\
&=1+C_p^1x+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+x^p\\
\end{aligned}
\]
\(\because p为质数\therefore1\sim p-1均与p互质\\\therefore C_p^2,C_p^3,\cdots,C_p^{p-1}均能整除p,即C_p^2,C_p^3,\cdots,C_p^{p-1}\,mod\,p=0\)
\[(1+x)^p\equiv(1+x^p)\,mod\,p\tag{2}
\]
\]
即 \((1+x)^p\) 在模 \(p\) 的意义下与 \((1+x^p)\) 同余。
根据 \((1+x)^a\) 求解 \(C_b^a\)
设 \(a=\lfloor \frac{a}{p}\rfloor p+a\%p\)，\(a’=\lfloor \frac{a}{p}\rfloor\) 有：
\[\begin{aligned}
(1+x)^a&=(1+x)^{\lfloor \frac{a}{p}\rfloor p+a\%p}\\
&=(1+x)^{a’p+a\%p}\\
&=(1+x)^{a’p}(1+x)^{a\%p}\\
\because a\%p=a_0
\therefore &=(1+x)^{a’p}(1+x)^{a_0}\\
&=\underline{((1+x)^p)^{a’}}(1+x)^{a_0}\\
\because公式(2)
\therefore &=\underline{(1+x^p)^{a’}(1+x)^{a_0}}
\end{aligned}\tag{3}
\]
(1+x)^a&=(1+x)^{\lfloor \frac{a}{p}\rfloor p+a\%p}\\
&=(1+x)^{a’p+a\%p}\\
&=(1+x)^{a’p}(1+x)^{a\%p}\\
\because a\%p=a_0
\therefore &=(1+x)^{a’p}(1+x)^{a_0}\\
&=\underline{((1+x)^p)^{a’}}(1+x)^{a_0}\\
\because公式(2)
\therefore &=\underline{(1+x^p)^{a’}(1+x)^{a_0}}
\end{aligned}\tag{3}
\]
再设 \(a’=\lfloor \frac{a’}{p}\rfloor p+a’\%p\)，\(a”=\lfloor \frac{a’}{p}\rfloor\) 有：
\[\begin{aligned}
((1+x)^p)^{a’}&=(1+x^p)^{\lfloor \frac{a’}{p}\rfloor p+a’\%p}\\
&=(1+x^p)^{a”p+a’\%p}\\
&=(1+x^p)^{a”p}((1+x)^p)^{a’\%p}\\
\because a’\%p=a_1
\therefore &=(1+x^p)^{a”p}((1+x)^p)^{a_1}\\
&=\underline{(1+x^p)^p)^{a”}((1+x)^p)^{a_1}}\\
\because公式(2)
\therefore &=\underline{(1+x^{p^2})^{a”}(1+x^p)^{a_1}}
\end{aligned}\tag{4}
\]
((1+x)^p)^{a’}&=(1+x^p)^{\lfloor \frac{a’}{p}\rfloor p+a’\%p}\\
&=(1+x^p)^{a”p+a’\%p}\\
&=(1+x^p)^{a”p}((1+x)^p)^{a’\%p}\\
\because a’\%p=a_1
\therefore &=(1+x^p)^{a”p}((1+x)^p)^{a_1}\\
&=\underline{(1+x^p)^p)^{a”}((1+x)^p)^{a_1}}\\
\because公式(2)
\therefore &=\underline{(1+x^{p^2})^{a”}(1+x^p)^{a_1}}
\end{aligned}\tag{4}
\]
同理，可得到
\[(1+x^{p^2})^{a”}=(1+x^{p^3})^{a”’}\underline{(1+x^{p^2})^{a_2}}
\]
\]
这样经过不断的迭代，最终得到:
\[(1+x)^a=(1+x^{p^k})^{a_k}*(1+x^{p^{k-1}})^{a_{k-1}}
*\cdots*(1+x^p)^{a_1}*(1+x)^{a_0}\tag{5}
\]
*\cdots*(1+x^p)^{a_1}*(1+x)^{a_0}\tag{5}
\]
等式两边运用二项式分别求 \(C_a^bx^b\) ,右边可以看作 \(b\) 个球分到了 \(k\)个 盒子里，每个盒子里面得数量就是 \(b_i(1\le i\le k)\) 得
\[\begin{aligned}
C_a^bx^b&=C_{a_k}^{b_k}x^{p^kb_k}C_{a_{k-1}}^{b_{k-1}}x^{p^{k-1}b_{k-1}}\cdots C_{a_1}^{b_1}x^{pb_1}C_{a_0}^{b_0}x^{b_0}\\
&=(\prod_{i=0}^k{C_{a_i}^{b_i}})(x^{\sum_{i=0}^{k}{p^ib_i}})\\
\because 公式(1)中b的展开式
\therefore &=(\prod_{i=0}^k{C_{a_i}^{b_i}})x^b\\
\end{aligned}
\]
C_a^bx^b&=C_{a_k}^{b_k}x^{p^kb_k}C_{a_{k-1}}^{b_{k-1}}x^{p^{k-1}b_{k-1}}\cdots C_{a_1}^{b_1}x^{pb_1}C_{a_0}^{b_0}x^{b_0}\\
&=(\prod_{i=0}^k{C_{a_i}^{b_i}})(x^{\sum_{i=0}^{k}{p^ib_i}})\\
\because 公式(1)中b的展开式
\therefore &=(\prod_{i=0}^k{C_{a_i}^{b_i}})x^b\\
\end{aligned}
\]
等式两边同时消去 \(x^b\) ，得：
\[C_a^b\,mod\,p\equiv \prod_{i=0}^{k}{C_{a_i}^{b_i}}\tag{6}
\]
\]
根据递归的过程，也可写成：
\[C_a^b\,mod\,p=C_{a/p}^{b/p}C_{a\%p}^{b\%p}\tag{7}
\]
\]
例题：
下面以AcWing 887. 求组合数 III为例：传送门
- 使用 \(Lucas\) 定理主要使用公式\(7\)的递推式
- 函数
int C(int a, int b)实现\(C_a^b\)的求解，使用\(C_a^b=\frac{a*(a-1)*\cdots*(a-b+1)}{b*(b-1)*\cdots*1}\),分子用逆元即可 - 参考y总：传送门
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int p;
int qmi(int a, int b) {
int res=1;
while(b) {
if(b&1) res=(ll)res*a%p;
a=(ll)a*a%p;
b>>=1;
}
return res;
}
int C(int a, int b) {
int res=1;
for(int i=1,j=a;i<=b;++i,--j) {
res=(ll)res*j%p;
res=(ll)res*qmi(i,p-2)%p;
}
return res;
}
int lucas(ll a, ll b) {
if(a<p&&b<p) return C(a,b);
return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // ONLINE_JUDGE
scanf("%d",&n);
while(n--) {
ll a,b;
scanf("%lld%lld%lld",&a,&b,&p);
printf("%d\n",lucas(a,b));
}
return 0;
}
