卢卡斯定理（前置：二项式定理 费马小定理）

写完才发现基本就是余ay博客里的一样。。
定理：
$(^n _ m)=(^{n/p}_ {m/p})\times (^{n \% p}_ {m \% p})(mod p)$
这样当$p$比较小的时候就可以快速处理出很大的组合数。

一个小性质：
当$n\%p < m\%p$时，$(^n_ m) \equiv 0(mod p)$
设$n=ap+b,m=cp+d$
此时$b<d$，所以$n-m=(a-c-1)p+(p+b-d)$
这样会$n!$中所含的$p$的倍数的个数为$a$，$m!(n-m)!$中所含的$p$的倍数的个数为$a-1$
还没有考虑$n!$中出现$p^k(k>1)$的频率更高的问题。
这样$\frac{n!}{m!(n-m)!}$一定就是$p$的倍数了

前置：二项式定理（其实就是暴力展开……）
$(a+b)^n=\sum_{i=0}^n (^n _i) a^ib^{n-i}$

前置：费马小定理
$a^{p-1} \equiv 1(mod p)$（p是质数）

所以：
$x \equiv x^p(mod p)$
$(1+x)^p \equiv 1+x \equiv 1+x^p (mod p)$

这里通过二项式定理证明。

(设$a=n/p,b=n\%p,c=m/p,d=m\%p$)
现在有：

$(1+x)^n \equiv (1+x)^a \times (1+x)^b (mod p)$
$(1+x)^n \equiv (1+x^p)^a \times (1+x)^b(mod p)$
$(1+x)^n \equiv \sum_ {i=0} ^a(^a_ i)x^{i*p} \times \sum_ {j=0} ^b(^b_ j)x^{j}(mod p)$
同时根据二项式定理有：
$(1+x)^n \equiv \sum_ {i=0} ^n(^n_ i)x^i(mod p)$
观察一下这两个式子第$m$项的系数
$(^n_ m)$和$(^a_ i)(^b_ j)(i<p,j<p)$
然而右边那个带回原字母定义有$(^{n/p}_ {m/p}) \times (^{n\%p}_ {m\%p})$
OAO