Lucas定理
Lucas定理的证明：
(C_n^m=C_{ n \% P }^{ m\%P} C_{n/P}^{m/P} (mod P) ,P为质数)
设(m'=lfloor frac{m}{P} floor * P,n'=n-m\%P)
(将左边的分式中每一个因式都模上P（因为分母每一个因式都与P互质），发现它就等于C_{n\%P}^{m\%P})
(然后发现右式分子分母中非P的倍数的项可以约去，只剩P的倍数项，然后再上下同除P，就会变成C_{n'/P}^{m'/P})
(又因为m'/P=m/P，而当C_{n\%P}^{m\%P}非0时n'/P=n/P，所以最终式子变成了C_{n/P}^{m/P})
(注意P为质数这个条件很重要，不然分子分母中非P的倍数的项就不能模P，也不能约去了)
举个例子：
(P=3)
(C_{11}^8=frac{11*10...*4}{8*7...*1}=frac{11*10}{8*7}*frac{9*8...*5}{6*5...*1}=frac{2*1}{2*1}*frac{9*6}{6*3}=frac{2*1}{2*1}*frac{3*2}{2*1}=C_2^2C_3^2)
多项式Exp
关于Exp做快速幂的疑问：用Exp计算(f^{mod}(x))的时候，先求ln，然后每一项系数乘以mod，这样多项式的值就变成了0，然后再exp，那么得到的(f^{mod}(x)=1) 。但是这样不合逻辑，因为如果(f(x)=x+1) ，那么(f^{mod}(x)[x^{mod}]=C_{mod}^{mod}=1) ，并不会等于0。
但仔细想想发现并不是这样，我们回忆一下求ln的过程，最后需要积分，而积分时正好就会在(x^{mod}) 项上乘一个(frac{1}{mod}) ，然后我们再给每一项乘一个(mod) ，那么(x^{mod}) 项上就不是0而是1了，这样Exp出来的结果就不会有问题。
有一个结论：
若(mod)为质数，(f(x))为一个多项式，那么在模(mod)意义下：
(f^{mod}(x)[x^0]=(f(x)[x^0])^{mod})
(f^{mod}(x)[x^{mod}]=(f(x)[x^1])^{mod})
(f^{mod}(x)[x^{k*mod}]=(f(x)[x^k])^{mod})
(其他非mod 的倍数次方项均为0)
可以用排列组合的方法证明。
同样的，我们可以用这个结论来证明Lucas定理：
设模数为(P)
取其([x^m])次项，则有(C_n^m=C_{ n \% P }^{ m\%P} C_{n/P}^{m/P} (mod P))