【学习笔记】卢卡斯定理
NCC79601
2019-04-02 13:55:51
卢卡斯定理是用于求$C_m^n\mod p$的一种算法。
### 定理
$$C_m^n\equiv C_{m\mod p}^{n\mod p}\times C_{m/p}^{n/p}(\mod p)$$
### 推导
首先，对于$C_m^n$有：
$$C_m^n=\frac{m!}{n!(m-n)!}=\frac{m}{n}\cdot\frac{(m-1)!}{(n-1)!(m-n)!}=\frac mn\cdot C_{m-1}^{n-1}$$
由二项式定理：
$$(a+b)^n=\sum_{i=0}^nC_n^ia^{n-i}b^i$$
因此可知：
$$(1+x)^p\equiv \sum_{i=0}^p C_p^ix^i\equiv C_p^01^px^0+C_p^p1^0x^p\equiv 1+x^p(\mod p)$$
取首尾两式整理得：
$$(1+x)^p\equiv 1+x^p(\mod p)$$
由这个性质，设$m=k_1p+r_1,n=k_2p+r_2$，有：
$$C_m^n\equiv C_{k_1p}^{k_2p}\cdot C_{r_1}^{r_2}(\mod p)$$
所以从一个二项式开始展开：
$$(1+x)^m=(1+x)^{k_1p+r_1}=(1+x)^{k_1p}\cdot(1+x)^{r_1}$$
$$\because (1+x)^{k_1p}\equiv((1+x)^p)^{k_1}\equiv(1+x^p)^{k_1}(\mod p)$$
$$\therefore (1+x)^n\equiv (1+x^p)^{k_1}\cdot(1+x)^{r_1}(\mod p)$$
找到$x^n$项：
$$\because C_m^nx^n\equiv (C_{k_1}^{k_2}\cdot x^{k_2p})( C_{r_1}^{r_2}\cdot x^{r_2})\equiv C_{k_1}^{k_2}\cdot C_{r_1}^{r_2}x^n (\mod p)$$
$$\therefore \text{约掉}x^n\text{可得：}C_m^n\equiv C_{k_1}^{k_2}\cdot C_{r_1}^{r_2}$$
### 应用
因为卢卡斯定理可以把一个巨大的组合数给拆掉，所以利用这个性质就能够求出$C_m^n \mod p$，也就是说：
$$C_m^n\equiv C_{m_0}^{n_0}\cdot C_{m_1p}^{n_1p}\cdot C_{m_2p^2}^{n_2p^2}\cdots (\mod p)$$
$$C_m^n\equiv \prod_{i=0}C_{m_ip^i}^{n_ip_i}(\mod p)$$
可联想到**快速幂**，先把$m$和$n$拆成$p$进制数，然后直接暴力计算就可以了。
## 模板 [P3807](https://www.luogu.org/problemnew/show/P3807)
**注意：** 题目要求的是$C_{n+m}^m\mod p$，所以输入的时候稍微不太一样。
可以留意如何将一个数拆成$p$进制数，操作较为高级。
---
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
long long a[MAXN];
int p;
inline long long Pow(long long base, int k) {
long long res = 1;
base %= p;
for(register int i = k; i; i >>= 1) {
if(i & 1)
res = res * base % p;
base = base * base % p;
}
return res % p;
}
inline long long C(long long m, long long n) {
if(m < n)
return 0;
if(m == n || n == 0)
return 1;
if(n == 1)
return m;
return a[m] * Pow(a[n], p-2) % p * Pow(a[m-n], p-2) % p;
}
inline long long Lucas(long long m, long long n) {
if(!n)
return 1;
return C(m % p, n % p) * Lucas(m/p, n/p) % p;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
long long m, n;
scanf("%lli%lli%lli", &n, &m, &p);
a[0] = 1;
for(register int i = 1; i <= p; i++)
a[i] = (a[i-1] * i) % p;
printf("%lli\n", Lucas(n + m, m));
}
return 0;
}
```