「知识总结」组合数问题 - Lucas 定理【Lucas】

简介

Lucas\text {Lucas} 定理是解决组合数问题的一个常用方法。

方法

pp 为质数,则对于任意 1mn1 \leqslant m \leqslant n,有

CnmCn mod pm mod pCn/pm/p(mod p)C_n^m \equiv C_{n \text{ mod } p}^{m \text{ mod } p} \cdot C_{n/p}^{m/p} \quad (\text{mod } p)

也记作:

(nm)(n mod pm mod p)(n/pm/p)(mod p)\binom{n}{m} \equiv \binom{n \text{ mod } p}{m \text{ mod } p} \cdot \binom{n/p}{m/p} \quad (\text{mod } p)

实现

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
// Luogu 3807

// 快速幂
ll pow(ll x, ll y, ll p) {
if (y == 0) return 1;
ll res = pow(x, y / 2, p);
res = res * res % p;
if (y % 2 == 1) res = res * x % p;
return res;
}

// 逆元, 按定义计算组合数
ll C(ll n, ll m, ll p) {
if (m > n) {
return 0;
}
return fact[n] * pow(fact[m], p - 2, p) % p * pow(fact[n - m], p - 2, p) % p;
}

// Lucas 定理
ll lucas(ll n, ll m, ll p) {
if (m == 0) {
return 1;
}
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}