卢卡斯定理/Lucas 定理
引入
求 \(C_{n+m}^n \mod p\)。
\(n,m,p \leq 10^5\)。
如果直接用阶乘求，可能在阶乘过程中出现了 \(p\)，而最后的结果没有出现 \(p\)，导致错误。
有两种解决方法：
1.求组合数时提前把 \(p\) 的质因子除掉。
2.Lucas 定理。
所以 Lucas 定理用于处理模数较小且为质数的情况下，求组合数的问题。
定理推导
先放结论：
\[C_a^b \equiv C_{\lfloor \frac{a}{p} \rfloor}^{\lfloor \frac{b}{p} \rfloor} \cdot C_{a \mod p}^{b \mod p} \mod p
\]
先证明 \(C_p^i \equiv \frac{p}{i}C_{p-1}^{i-1} \equiv 0 \mod p\)。
\[C_p^i=\frac{p!}{i!(p-i)!}=\frac{p}{i} \cdot \frac{(p-1)!}{(i-1)!(p-i)!}=\frac{p}{i}C_{p-1}^{i-1}
\]
得证。
考虑二项式定理，易得：
\[(1+x)^p \equiv C_p^0+C_{p}^1x+C_{p}^2x^2+\cdots+C_p^px^p \equiv 1+x^p \mod p
\]
Ps：除去 \(C_p^p=1\) 以外，其他的项都被模为 \(0\)。
此时，令 \(a=lp+r,b=sp+j\)。
求证 \(C_a^b \equiv C_l^s\cdot C_r^j \mod p\)。
接着剥削二项式
\[(1+x)^a=(1+x)^{lp}(1+x)^r
\]
展开 \((1+x)^{lp}\)
\[(1+x)^{lp} \equiv ((1+x)^p)^l \equiv (1+x^p)^l \mod p
\]
\[\therefore (1+x)^a \equiv (1+x^p)^l(1+x)^r \mod p
\]
通过上式，观察 \(x^b\) 项。
\[\because C_a^b x^b \equiv C_l^sx^{sp}\cdot C_r^jx^j \mod p \\
\therefore C_a^b x^b \equiv C_l^sC_r^jx^b \mod p \\
\therefore C_a^b \equiv C_{\lfloor \frac{a}{p} \rfloor}^{\lfloor \frac{b}{p} \rfloor} \cdot C_{a \mod p}^{b \mod p} \mod p
\]
Ps：左边是直接二项式的 \(x^b\) 项，右边是二项式 \((1+x^p)^l\) 的 \(x^{sp}\) 和 \((1+x)^r\) 的 \(x^j\) 项。