Lucas定理学习笔记

· · 个人记录

前言

学了很久这几个数论定理，但还没写个笔记，现在补起来。

正文

1.概念

在oi wiki中，lucas定理的定义是这样的：

Lucas 定理用于求解大组合数取模的问题，其中 p 必须为素数。正常的组合数运算可以通过递推公式求解（详见 排列组合 ），但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 Lucas 定理。

简单来说，就是解决 C^n_m \ mod\ p,(p\ is\ a\ prime) 的值，它可以做到 log 级别的优秀复杂度。

2.证明

注：本文中的除法都认为自动下取整，且 p 默认都为质数，所有数均为正整数

首先先上结论：

C^n_m\ mod\ p =C^{\frac{n}{p}}_ {\frac{m}{p}}\times C^{n\ mod\ p }_ {m\ mod\ p}

接下来我们要证明这个结论，先上两个引理：

引理1：

\forall \ i\ | 1\le i < p,C^i_p \equiv 0(mod\ p)

这个是较为显然的，将 C^i_p 暴力展开:

\displaystyle C^i_p=\frac{\prod\limits^p_{j=p-i+1}j}{\prod\limits^i_{k=1}k}

显然，分子上的 k 是绝对不可能为 p 的因数的 (因为 k<p 且 p 是个质数)，所以 C^i_p 必定为 p 的倍数

引理2：

(1+x)^p \equiv 1+x^p\ (mod\ p)

这个东西的左边我们先按照二项式定理展开：

(1+x)^p=\sum^p_{i=0}C^i_px^p \because \forall \ i\ | 1\le i < p,C^i_p \equiv 0(mod\ p) \therefore(1+x)^p=\sum^p_{i=0}C^i_px^p \equiv 1+x^p\ (mod\ p)

有了这两个引理，我们就可以简单的证出Lucas定理了

设 n=sp+q,m=rp+t(q,t<p)

则我们考虑一个奇怪的东西：

(1+x)^m=(1+x)^{rp+t}

我们要求的 C^n_m即是其中 n 次项的系数

将有 p 的指数与没 p 的指数分离，可得：

(1+x)^{rp+t}=(1+x)^{rp}\times (1+x)^t=((1+x)^{p})^r\times (1+x)^t \quad ( * )

使用引理二，我们可得：

((1+x)^{p})^r\times (1+x)^t=(1+x^p)^r\times (1+x)^t

同时，我们把要求的 n 次项写出来：

x^n=x^{sp+q}

发现 n 次项的系数在最新的式子中应该是由 (x^p)^s 与 x^t 拟合而成，这一项的系数应为 (x^p)^s 在 * 式前半部分与* 式后半部分系数相乘而得，计算可得系数应为：

C^s_r \times C^q_t

看到原来的式子中 n 次项的系数为：

C^n_m

所以我们得到了：

C^n_m\equiv C^s_r \times C^q_t(mod p)

即：

C^n_m\ mod\ p =C^{\frac{n}{p}}_ {\frac{m}{p}}\times C^{n\ mod\ p }_ {m\ mod\ p}

3.代码实践

观察我们的柿子，其实我们只需要算出 C^{n\ mod\ p }_ {m\ mod\ p} 即可，C^{\frac{n}{p}}_ {\frac{m}{p}}可以继续递归直到 n,m\le p

根据组合数的计算公式：

C^n_m=\frac{m!}{n!(m-n)!}

所以我们可以预处理出 1 到 p 的阶乘与阶乘逆元，O(1) 计算组合数，整个算法也就结束了

下面附上核心代码：

int lucas(int m,int n,int p)
{
    if(m<p)
     return C(m,n);
    return lucas(m/p,n/p,p)*C(m%p,n%p)%p;
}

简简单单，只有五行，但是其中的证明还需要多思考

End