卢卡斯(Lucas)定理

看了看网上关于 $Lucas$ 的讲解，感觉很多充斥着大量难懂的公式，对于小学生初学者来说不太友好，于是决定写一篇没有任何算法数学基础的人都能看懂的 $Lucas$ 。（当然本文中也会出现一些公式，不过没有 $\sum$ 这种令人难受的符号而且公式大多特别简单）

$Lucas$ 定理主要用于大组合数取膜。

他的结论很简单：当且仅当 $p$ 为质数时，$C_m^{n}modp=C_{mmodp}^{nmodp}\times C_{m÷p}^{n÷p}modp$

由于作者太弱并不会证明，如果对恶心的证明感兴趣可以左转百度。

在 $n,m$ 很大而 $p$ 又很小的时候就可以使用 $Lucas$ 定理。

写个递归就可以实现 $Lucas$ 定理啦（本文所有代码均默认已经添加了typedef long long ll）！

inline ll Lucas(ll m, ll n) { return n == 0 ? 1 : C(m % p, n % p) * Lucas(m / p, n / p) % p; }

慢着，你以为这就完了？

$Lucas$ 函数已经很优秀了，可是组合数如果按照杨辉三角计算…… $Lucas$ 复杂度+n。

按公式计算呢？炸了。

这里科普一个叫逆元的东西，它是拿来干啥的呢？

我们知道：

$(a+b)modp=(amodp+bmodp)modp$ $(a+b)modp=(amodp-bmodp+p)modp$ $(a\times b)modp=(amodp\times bmodp)modp$

可是除法……就很讨厌了，他不满足模运算的“分配律”。

那么，我们可以考虑将除法强行变成除法：

$(a÷b)modp=(amodp\times b‘modp)modp$

这里的 $b‘$ 就是 $b$ 的逆元。

逆元定义：若存在 $a\times xmodp=1$，则称 $x$ 为 $a$ 在膜 $p$ 意义下的逆元。

求逆元一般有三种方法：$exgcd$，费马小定理，线性求逆。其中费马小定理是最简单的一种方法。

费马小定理：若 $gcd(a,p)=1$，则 $p|a^{p-1}-1$，即 $p$ 整除 $a^{p-1}-1$。也就是说，$a^{p-1}-1modp=1$。这不就是逆元的定义？于是我们可以得出 $a$ 的逆元：$a^{p-2}modp$。

用 $exgcd$ 可以证明，逆元方程仅当 $gcd(a,p)=1$ 时有解，否则无解。这部分的证明如果不想看可以跳到加粗的”结论“后面的“所以”。

$$\begin{gathered} \because a\cdot xmodp=1 \\ \therefore a\cdot x-1modp=0 \\ \therefore a\cdot x-1=p\cdot y(y\in N) \\ \therefore a\cdot x-p\cdot y=1 \\ \therefore a\cdot x+b\cdot y=1(b=-p) \end{gathered}$$

下面对方程 $a\cdot x+b\cdot y$ 进行讨论：

$$\begin{gathered} 若有解a\cdot x0+b\cdot y0 \\ 如果还有解a\cdot x1+b\cdot y1 \\ 则a\cdot x0+b\cdot y0=a\cdot x1+b\cdot y1 \\ 移项得a\cdot (x0-x1)=b\cdot (y1-y0) \\ 将方程两边同时除以gcd(a,b) \\ 得a0\cdot (x0-x1)=b0\cdot (y1-y0) \\ 此时a0和b0互素。因此b0|x0-x1 \\ 设k\cdot b0=x0-x1 \\ 则y1-y0=k\cdot a0 \end{gathered}$$

结论： 设 $a,b,c$ 为任意整数，若方程 $a\cdot x+b\cdot y=c$ 的一组整数解为 $(x0,y0)$，则它的任意整数解都可以写成 $(x0+k\cdot b0,y0-k\cdot a0)$，其中 $a0=a/gcd(a,b),b0=b/gcd(a,b)$，$k$ 取任意整数。

所以，上文的逆元方程要有解，当且仅当 $1$ 是 $gcd(a,p)$ 的倍数，即 $gcd(a,p)=1$。

然后快速冥求出 $a^{p-2}modp$ 就行了？

快速冥求法：对于 $a^b$，当 $b$ 为奇数时 $a^b=a^{(b-1)/2}\times a^{(b-1)/2}modp\times amodp$。否则等于 $a^{b/2}\times a^{b/2}modp$。

写个迭代就可以求出快速冥和逆元了！

inline ll quickpow(ll a, ll b) { register ll res(1); a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res % p; } inline ll inv(ll a, ll p) {//求a在膜p意义下的逆元 return quickpow(a, p - 2); }

组合数代码：

inline ll C(ll m, ll n) { return m < n ? 0 : fact[m] * inv(fact[n], p) % p * inv(fact[m - n], p) % p;//逆元取模，fact[i]表示i的阶乘，如果p大于1e6必须现算阶乘 }

完整代码：

//输入n,m，p,求C{n,m}%p(p<=1000000) #include <cstdio> typedef long long ll; ll fact[1000005], p; inline void Init() { fact[1] = 1; for (register int i(2); i <= p; ++ i) fact[i] = fact[i - 1] * i % p; } inline ll quickpow(ll a, ll b) { register ll res(1); a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res % p; } inline ll inv(ll a, ll p) { return quickpow(a, p - 2); } inline ll C(ll m, ll n) { return m < n ? 0 : fact[m] * inv(fact[n], p) % p * inv(fact[m - n], p) % p; } inline ll Lucas(ll m, ll n) { return n == 0 ? 1 : C(m % p, n % p) * Lucas(m / p, n / p) % p; } int main() { ll n, m; scanf("%lld%lld%lld", &n, &m, &p); Init(); printf("%lld", Lucas(n, m)); }

最后别忘了 $Lucas$ 只适用于模数为质数且不超过1e6的情况，如果模数可能为合数要用的作者不会的扩展 $Lucas$ 定理。代码时间复杂度为 $O(plo{g}_p)$，如果加个线性求逆元的预处理可以达到 $O(p+lo{g}_{p}n)$