卢卡斯定理

  |  

摘要: 求组合数的代码模板和例题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


爱德华·卢卡斯(1842-1891)

卢卡斯定理是由法国数学家爱德华·卢卡斯在1878年提出的,涉及到组合数和模运算,广泛应用于组合数学和数论中。

卢卡斯定理

设 p 是一个素数,将 m 和 n 写成 p 进制数:

其中:$0 \leq a_{i}, b_{i} < p (i=0,1,\cdots,k)$,则:

证明:二项式定理+比较系数

注意到 $1 \leq j \leq p^{i} - 1, i \geq 1$ 时,$\binom{p^{i}}{j}$ 是 $p$ 的倍数,故:

而上式在 $i=0$ 时,显然成立。因此:

上式左边 $x^{m}$ 的系数为 $\binom{n}{m}$

注意到 $m$ 表示成 p 进制数的唯一性,由 $m = \sum\limits_{i=0}\limits^{k}b_{i}p^{i}$,得上式右端 $x^{m}$ 的系数为:

因此:

卢卡斯定理推论

令 $n = sp + q$,$m = tp + r$,$(q, r \leq p)$,则:

证明

将 n, m 用 p 进制数表示,如下:

由卢卡斯定理:

对比 $n = sp + q$,$m = tp + r$ 及其 p 进制表示,有:

由卢卡斯定理:

于是:

求大组合数模质数

如果要算 $\binom{n}{m}\mod{p}$,则可以用卢卡斯定理。

记 $Lucas(n, m, p) = \binom{n}{m}\mod{p}$,$n = sp + q$, $m = tp + r$,由卢卡斯定理的推论,公式如下:

代码模板 (C++)

涉及到模下组合数、模下快速幂。

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
46
// 卢卡斯定理模板
// Lucas 定理实现 C(n,m) % p 的代码:
using ll = long long;
ll exp_mod(ll a, ll b, ll p)
{
//快速幂取模
ll res = 1;
while(b != 0)
{
if(b & 1) res = (res * a) % p;
a = (a * a) % p;
b >>= 1;
}
return res;
}

ll Comb(ll a, ll b, ll p)
{
//求组合数C(a,b) % p
if(a < b) return 0;
if(a == b) return 1;
if(b > a - b) b = a - b;

ll ans = 1, ca = 1, cb = 1;
for(ll i = 0; i < b; ++i)
{
ca = (ca * (a - i)) % p;
cb = (cb * (b - i)) % p;
}
ans = (ca * exp_mod(cb, p - 2, p)) % p;
return ans;
}

ll Lucas(ll n, ll m, ll p)
{
//Lucas定理求C(n,m)%p
ll ans = 1;

while(n && m && ans)
{
ans = (ans * Comb(n % p, m % p, p)) % p;
n /= p;
m /= p;
}
return ans;
}

关于卢卡斯定理的例题,以及与预处理结合的用法,参考文章 组合数


Share