省选后数论学习

　　省选差点被数论题送退役（指式子推复杂了，导致最后还有一个组合数模非质数，没写出来），决定重新学一些数论知识。

Lucas定理的证明

　　上来先写一个理性愉悦。

　　先来复习一下Lucas是啥：$\binom{n}{m} \% p$ ，其中n,m比较大，p是一个不太大的质数；复杂度是预处理 $O(p)$，每次询问 $O(\log_pm)$。

　　首先证明一个引理：$(1+x)^p\equiv1+x^p\pmod p$，考虑使用二项式定理展开左边，得到：

　　$\sum_{i=0}^p\binom{p}{i}x^i=\sum_{i=0}^p\frac{p!}{i!(p-i)!}x^i=\sum_{i=0}^p\frac{p(p-1)\dots(p-i+1)}{i!}x^i$

　　先不考虑 $i=0$ 的情况，在 $i\neq p$ 时，因为 $p$ 是质数，所以分子上的 $p$ 是不可能与分母约分的，也就是说，当 $i\neq p$ 时，$\binom{p}{i}x^i\equiv0 \pmod p$.即，$(1+x)^p=\sum_{i=0}^p\binom{p}{i}x^i=\binom{p}{p}x^p+\binom{p}{0}x^0=1+x^p\pmod{p}$

　　不停使用这个引理，得到：$(1+x)^{p^i}=1+x^{p^i}\pmod p$

　　当然，用费马小定理似乎也可以直接证明这个引理就是了...

　　现在整一个好玩的东西：组合数生成函数；

　　$f(x)=\sum_{i=0}^m\binom{m}{i}x^i=(1+x)^m$

　　对 $m$ 进行 $p$ 进制拆分：$m=\sum m_ip^i$

　　$f(x)=(1+x)^{\sum m_ip^i}=\prod(1+x)^{m_ip^i}=\prod((1+x)^{p^i})^{m_i}$

　　$=\prod (1+x^{p_i})^m=\prod \left(\sum\limits_{j=0}^{m_i}\binom{m_i}{j}x^{p^i\times j}\right)$

　　$=\prod\left(\sum\limits_{n_i=0}^{p-1}\binom{m_i}{n_i}x^{p^i\times n_i}\right)=\sum\left(\prod\binom{m_i}{n_i}\right)x^{\sum p^i n_i}$

　　我们将它和最早的形式放到一起，就可以得到：$\sum \binom{m}{n}x^n=\sum\left(\prod\binom{m_i}{n_i}\right)x^{\sum p^i n_i}$

　　两个生成函数相等，就意味着对应项的系数相等，可以得到：

　　$\binom{m}{n}=\prod\binom{m_i}{n_i}\pmod p$

　　于是就证明完啦。　　

省选后数论学习

原文：https://www.cnblogs.com/shzr/p/13205150.html