概念
卢卡斯定理要解决的问题很简单：
如果$p$规定为质数，那么就用卢卡斯定理解决，否则就是扩展卢卡斯定理。
洛谷上两个模板题都有 Lucas ExLucas
前置知识
如果你不知道前置的知识的话，最好还是去系统学习一下。
1. 乘法逆元
若$Ax \equiv 1 (mod~p)$且$A$与$p$互质，则称$A$的$mod~p$意义下的乘法逆元为$X$
关于求逆元：
因为$(a,p) = 1$
所以$a^{p-1} \equiv 1 (mod~p)$
所以$a \times a ^{p - 2} \equiv 1 (mod~p)$
所以$m!(n - m)!$的逆元为$(m!(n - m)!) ^{p - 2}$
直接快速幂就可以了。
2.扩展欧几里得
扩展欧几里得用来在求得$gcd(a,b)$的同时，找出整数$x,y$使其满足$ax + by = gcd(a,b)$
3.费马小定理
$a^(p-1) \equiv 1 (mod~p)$。
4.中国剩余定理
还请移步博客欧几里得与扩展中国剩余定理Excrt
卢卡斯定理
证明过程：
首先根据组合数的只是我们可以很显然推出
然后根据二项式定理得出：
然后我们继续从二项式定理推出：
上式也就是所谓的卢卡斯定理，这玩意的用处就在于下面这个递推式：
其中$Lucas(x,0,p) = 1$且$CC_m^n = (C_m^n)^(p-2) ~mod ~p$
实际上就是一个费马小定理和乘法逆元。
根据这个东西就可以很快地求出来上面的问题了。
如果你看不大懂，那就只需要记结论。。。。
然后直接递归调用$C_{m~mod~p}^{n~mod~p} ~mod~p$就可以了。
对于$C_m^n$的除法取模就需要用到逆元了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
LL N, M, P, X[MAXN] ;
inline LL Read() {
LL X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline LL QuickPow(LL A, LL B) {
LL Ans = 1 ; if (! B) return 1 % P ;
while (B) {
if (B & 1) Ans = Ans * A % P ;
A = A * A % P, B >>= 1 ;
} return Ans ;
}
inline LL C(LL A, LL B) {
if (B > A) return 0 ;
return (X[A] * QuickPow(X[B], P - 2)) % P * QuickPow(X[A - B], P - 2) % P ;
}
inline LL Lucas(LL A, LL B) {
if (! B) return 1 ;
else return (C(A % P, B % P) * Lucas(A / P, B / P)) % P ;
}
int main() {
int T = Read() ; while (T --) {
N = Read(), M = Read(), P = Read() ;
X[0] = 1 ;
for (LL i = 1 ; i <= P ; i ++)
X[i] = (X[i - 1] * i) % P ;
LL Ans = Lucas(N + M, N) ;
printf("%lld\n", Ans) ;
} return 0 ;
}
扩展卢卡斯定理
令$P = \prod p_i^{c_i}$
假设我们知道$C_n^m ~mod~p_i^{c_i}$就可以直接上$Crt$，但是我们并不知道。（泪目
怎么求呢？
对于$C^n_m = \frac{n!}{(n-m)!m!}$
我们可以阶乘的变换。
假设我们现在要求$19! % 3$
我们将$1 \times…\times 19$中所有$3$的倍数拿出来合并。
那么我们就得到$\lfloor \frac{19}{3} \rfloor$个满足项，然后除以$3$之后，就得到$\lfloor \frac{19}{3} \rfloor !$,这一部分不好算，我们直接递归下去。
然后对于其他的项，可以看出来他们具有小于$3^k$的循环节这种东西，就可以暴力。
然后时间复杂度就很可观了。