Lucas/exLucas 定理学习笔记-526互联

0x00 前言

Lucas 定理适用于求在模 p 意义下的组合数（p 是质数）。此时， p 一般不大，但 n,m 很大，这样无法通过常规的方法预处理（一是空间可能开不下，二是如果 m>p ，则 n-m 和 m 不一定有逆元）。

当然你可以用杨辉三角递推，但这是 \(\text{O}(n^2)\) 的。

0x01 方法

先上结论，当 p 为质数时，有 \(\dbinom{n}{m}\equiv\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\times\dbinom{n\bmod p}{m\bmod p}\pmod{p}\) 。当 n<m 时，规定 \(\dbinom{n}{m}=0\) 。

0x02 原理

就是证明这个柿子。

引理：若 x 是小于质数 p 的正整数，则 \(\dbinom{p}{x}\equiv0\pmod{p}\) 。

证明：因为 x<p ，则 x 存在关于 p 的逆元。 \(\dbinom{p}{x}\equiv\frac{p!}{x!(p-x)!}\equiv\frac{(p-1)!}{(x-1)!(p-x)!}\times\frac{p}{x}\equiv\dbinom{p-1}{x-1}\times p\times\text{inv}(x)\pmod{p}\) ，得证。

根据二项式定理，得到：\((1+x)^n=\sum\limits_{i=0}^n\dbinom{n}{i}x^i\equiv1+x^n\pmod{p}\) 。

下面开始证明：令 \(p_n=\left\lfloor\frac{n}{p}\right\rfloor,q_n=n\bmod p,p_m=\left\lfloor\frac{m}{p}\right\rfloor,q_m=m\bmod p\) 。

\[\begin{aligned} (1+x)^n&=(1+x)^{p_np+q_n}\\\\ &\equiv(1+x^p)^{p_n}(1+x)^{q_n}\\\\ &=\sum\limits_{i=0}^{p_n}\sum\limits_{j=0}^{q_n}\dbinom{p_n}{i}\dbinom{q_n}{j}x^{ip+j}\\\\ &=\sum\limits_{m=0}^n\dbinom{p_n}{p_m}\dbinom{q_n}{q_m}x^m\\\\ &\equiv\sum\limits_{m=0}^n\dbinom{n}{m}x^m\\\\ \end{aligned} \]

对比系数就可以得到上式。

0x03 实现

根据上式，可以通过递归的方式实现 Lucas 。

int C(int n,int m,int p){
	if(n<0||m<0||n-m<0)return 0;
	return jc[n]*ij[m]%p*ij[n-m]%p;
}
int Lucas(int n,int m,int p){
	if(n==0)return 1;
	return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}

时间复杂度 \(\text{O}(p+\log_p n)\) （线性预处理 p 以内的逆元）。