lucas定理

lucas定理的证明：

\(C_n^m=C_{ n \% P }^{ m\%P} C_{n/P}^{m/P}\ \ (mod\ P)\ ,P为质数\)

\[C_n^m=\frac{n(n-1)...(n-m+1)}{m(m-1)...*2*1}\]

设\(m'=\lfloor \frac{m}{P} \rfloor * P,n'=n-m\%P\)

\[C_n^m=\frac{n(n-1)...(n'+1)}{m(m-1)...(m'+1)}*\frac{n'(n'-1)...(n-m+1)}{m'(m'-1)...1}\]

\(将左边的分式中每一个因式都模上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\)

\[C_n^m=(1+x)^n[x^m]\]

\[(1+x)^n=(1+x)^{n\% P}[(1+x)^{n/P}]^P\]

\[=(\sum_{i=0}^{n\%P}C_{n\%P}^{i}x^i)(\sum_{i=0}^{n/P}C_{n/P}^{i}x^{iP})\]

\[=\sum_{i=0}^{n}C_{n/P}^{i/P}C_{n\%P}^{i\%P}x^i\]

取其\([x^m]\)次项，则有\(C_n^m=C_{ n \% P }^{ m\%P} C_{n/P}^{m/P}\ \ (mod\ P)\)