省选差点被数学题送退役（指式子推复杂了，导致最后还有一个组合数模非质数，没写出来），决定重新学一些数学知识。
Lucas定理的证明
上来先写一个理性愉悦。
先来复习一下Lucas是啥：$inom{n}{m} \% p$ ，其中n,m比较大，p是一个不太大的质数；复杂度是预处理 $O(p)$，每次询问 $O(log_pm)$。
首先证明一个引理：$(1+x)^pequiv1+x^ppmod p$，考虑使用二项式定理展开左边，得到：
$sum_{i=0}^pinom{p}{i}x^i=sum_{i=0}^pfrac{p!}{i!(p-i)!}x^i=sum_{i=0}^pfrac{p(p-1)dots(p-i+1)}{i!}x^i$
先不考虑 $i=0$ 的情况，在 $i eq p$ 时，因为 $p$ 是质数，所以分子上的 $p$ 是不可能与分母约分的，也就是说，当 $i eq p$ 时，$inom{p}{i}x^iequiv0 pmod p$.即，$(1+x)^p=sum_{i=0}^pinom{p}{i}x^i=inom{p}{p}x^p+inom{p}{0}x^0=1+x^ppmod{p}$
不停使用这个引理，得到：$(1+x)^{p^i}=1+x^{p^i}pmod p$
当然，用费马小定理似乎也可以直接证明这个引理就是了...
现在整一个好玩的东西：组合数生成函数；
$f(x)=sum_{i=0}^minom{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(sumlimits_{j=0}^{m_i}inom{m_i}{j}x^{p^i imes j} ight)$
$=prodleft(sumlimits_{n_i=0}^{p-1}inom{m_i}{n_i}x^{p^i imes n_i} ight)=sumleft(prodinom{m_i}{n_i} ight)x^{sum p^i n_i}$
我们将它和最早的形式放到一起，就可以得到：$sum inom{m}{n}x^n=sumleft(prodinom{m_i}{n_i} ight)x^{sum p^i n_i}$
两个生成函数相等，就意味着对应项的系数相等，可以得到：
$inom{m}{n}=prodinom{m_i}{n_i}pmod p$
于是就证明完啦。
斯特林数
第一类斯特林数：把n个数分为m个非空环的方案数；
递推：每个数可以选择自己新开一个环，或者插入之前任意一个数后边；
$egin{bmatrix} n\m end{bmatrix}=egin{bmatrix} n-1\m-1 end{bmatrix}+(n-1) imes egin{bmatrix} n-1\m end{bmatrix}$
第二类斯特林数：把n个数分为m个非空集合的方案数；
递推：每个数可以选择自己新开一个集合，也可以加入之前的任意一个集合；
$egin{Bmatrix} n\m end{Bmatrix}=egin{Bmatrix} n-1\m-1 end{Bmatrix}+m imes egin{Bmatrix} n-1\m end{Bmatrix}$
容斥计算法：考虑有几个集合是空的；（要乘以阶乘的倒数是因为斯特林数中的集合是不区分的，但容斥式子中却是按区分来做的）
$egin{Bmatrix} n\m end{Bmatrix}=frac{1}{m!}sum_{i=0}^m(-1)^iinom{m}{i}(m-i)^n$
既然第二类斯特林数可以用幂来表示，那幂也可以由第二类斯特林数表示，思路依然是考虑有几个空集合。
$n^k=sum_{i=0}^kinom{n}{i} imes i! imes egin{Bmatrix} k\i end{Bmatrix}$
（差点被上述式子送退役）
下降幂与上升幂
下降幂：$n^{underline{m}}=prod_{i=0}^{m-1} (n-i)$
普通幂转下降幂：$n^m=sum_{i=0}^m n^{underline{i}}egin {Bmatrix}m\iend{Bmatrix}$
证明：听上去很高级，其实就是 $n^k=sum_{i=0}^kinom{n}{i} imes i! imes egin{Bmatrix} k\i end{Bmatrix}$ 的另一种写法罢了...
上升幂：$n^{overline{m}}=prod_{i=0}^{m-1} (n+i)$
上升幂转普通幂：$n^{overline{m}}=sum_{i=0}^m n^{i}egin {bmatrix}m\iend{bmatrix}$
证明：采用数学归纳法：$egin{align} x^{overline{n}}&=(x+n-1)x^{overline{n-1}}\ &=(x+n-1)sum_{k=0}^n egin{bmatrix}n-1\k end{bmatrix}x^k\ &=sum_{k=0}^n egin{bmatrix}n-1\k end{bmatrix}x^{k+1}+sum_{k=0}^n egin{bmatrix}n-1\k end{bmatrix}x^k (n-1)\ &=sum_{k=1}^n egin{bmatrix}n-1\k-1 end{bmatrix}x^{k}+sum_{k=0}^n egin{bmatrix}n-1\k end{bmatrix}x^k (n-1)\ &=sum_{k=0}^n x^k (egin{bmatrix} n-1\k-1end{bmatrix}+(n-1)egin{bmatrix}n-1\kend{bmatrix})\ &=sum_{k=0}^n egin{bmatrix}n\kend{bmatrix} x^kend{align}$
上升幂转下降幂：$x^{overline n}=(-1)^n(-x)^{underline{n}}$
下降幂转上升幂：$x^{underline n}=(-1)^n(-x)^{overline{n}}$
自然数幂次方和
自然数幂次方和指的是这样的问题：$S_k(n)=sum_{i=0}^ni^k$
先介绍一个用第二类斯特林数解决的方案，该方案适合k小，n大的情况。
$S_k(n)=sum_{i=0}^ni^k$
$=sum_{i=0}^nsum_{j=0}^kinom{i}{j} imes j! imes egin{Bmatrix} k\j end{Bmatrix}$
$=sum_{j=0}^kj! imes egin{Bmatrix} k\j end{Bmatrix}sum_{i=0}^ninom{i}{j}$
后面那个组合数的和怎么计算呢？考虑组合意义，对于任意一个 $inom{i}{j}$ 的方案，我们再额外选一个i+1进去...这样每种方案就相当于“在n+1个中选出j+1个”。也就是说 $sum_{i=0}^ninom{i}{j}=inom{n+1}{j+1}$;
$S_k(n)=sum_{j=0}^kj! imes egin{Bmatrix} k\j end{Bmatrix}inom{n+1}{j+1}$
这样就能快速计算自然数幂之和啦！