卢卡斯定理
求\(C_m^n~mod~p\)
设\(m={a_0}^{p_0}+{a_1}^{p_1}+\cdots+{a_k}^{p_k},n={b_0}^{p_0}+{b_1}^{p_1}+\cdots+{b_k}^{p_k}\)
则\(C_m^n\equiv\prod{C_{a_i}^{b_i}}(mod~p)\)
扩展卢卡斯定理
好像这也不是什么定理，只是一个计算方法
计算\(C_m^n~mod~p\)，其中\(p={p_1}^{q_1}\times{p_2}^{q_2}\times\cdots{p_k}^{q_k}\)时，我们可以先求出\(C_m^n~mod~{p_i}^{q_i}\)，然后用CRT合并。
那么怎么计算\(C_m^n~mod~{p_i}^{q_i}\)呢？
\(C_m^n=\frac{m!}{n!(m-n)!}\)，我们只需要算出\(m!,{n!}^{-1},{(m-n)!}^{-1}\)，然后乘在一起。
zjt大爷：\(n!\)可能在模\({p_i}^{q_i}\)的意义下没有逆元啊，那这就是错的了啊
其实这里求得不是逆元（可能没有逆元），求出来的是\(a\times {p_i}^b(gcd(a,p)=1)\)，前面的\(a\)用逆元，后面的次数加加减减一下就好了
问题转换成求\(n!~mod~p^q\)
例如\(n=19,p=3,q=2\)：
\[
\begin{align}
&19!\\
=&1\times2\times3\times\cdots\times19\\
=&(1\times2\times4\times5\times7\times8\cdots\times16\times17\times19)\times(3\times6\times9\times12\times15\times18)\\
=&(1\times2\times4\times5\times7\times8\cdots\times16\times17)\times19\times3^6\times(1\times2\times3\times4\times5\times6)\\
=&{(1\times2\times4\times5\times7\times8)}^2\times19\times3^6\times(1\times2\times3\times4\times5\times6)
\end{align}
\]
上面这个式子分为四部分：
第一部分：\({(1\times2\times4\times5\times7\times8)}^2\)。这部分的数不超过\(p^q\)个，可以暴力算
第二部分：\(19\)。这部分的数不超过\(p^q\)个，可以暴力算
第三部分：\(3^6\)。这个在最后处理时求出\(m!,n!,(m-n)!\)分别有多少个\(p\)（设为\(x,y,z\)），则答案要乘上\(p^{x-y-z}\)
第四部分：\(1\times2\times3\times4\times5\times6\)。这个是\(\lfloor\frac{n}{p}\rfloor!\)，可以递归处理