Lucas定理

问题：求$C_n^m\mod p$，其中保证$p$为质数。

将$n,m$进行$p$进制展开：

$$n=\sum_{i=0}^k n_ip^i\\ m=\sum_{i=0}^k m_ip^i\\$$

则有

$$C_n^m \equiv \prod_{i=0}^k C_{n_i}^{m_i} \mod p$$

这就是Lucas定理。

利用生成函数证明：

首先，易得$\forall 0< i < p,p\mid C_p^i$

$\therefore (1+x)^p\equiv 1+x^p\mod p,(1+x)^{p^i}\equiv 1+x^{p^i}\mod p$

我们的目的是证明：$\sum_{m=0}^n C_n^mx^m=\sum_{m=0}^n(\prod_{i=0}^kC_{n_i}^{m_i})x^m\mod p$

$$\sum_{m=0}^n C_n^m x^m\\ =(1+x)^n\\ =\prod_{i=0}^k (1+x)^{n_ip^i}\\ =\prod_{i=0}^k ((1+x)^{p^i})^{n_i}\\ =\prod_{i=0}^k (1+x^{p^i})^{n_i}$$

这个时候对里面的这一项再进行二项式展开：

$$\prod_{i=0}^k (1+x^{p^i})^{n_i}\\ =\prod_{i=0}^k (\sum_{m_i=0}^{n_i}C_{n_i}^{m_i} x^{n_i{p^i}})$$

由于当$m_i>n_i$时$C_{n_i}^{m_i}=0$，所以上面的式子可以等价地写成：

$$\prod_{i=0}^k(\sum_{m_i=0}^{p-1}C_{n_i}^{m_i}x^{n_ip^i})$$

考虑这个函数的$x^{m’}$次项，由于$m’$的$p$进制展开是唯一的，所以这一项的系数一定恰好等于$\prod C_{n_i}^{m’_i}$，其中$m’_i$为$m’$的$p$进制展开。

也就是说，这个函数等于$\sum_{m=0}^n(\prod_{i=0}^kC_{n_i}^{m_i})x^m$。得证。

另外一种证明方式：设$n=kp+r,m=ap+b$，其中$r< p$，则

$$(1+x)^n\\ =(1+x)^{kp}(1+x)^r\\ =(1+x^p)^k(1+x)^r\\ =\sum_{i=0}^kC_k^ix^{pi}\sum_{j=0}^rC_r^j x^j\\ =\sum_{i=0}^k\sum_{j=0}^rC_k^iC_r^jx^{pi+j}$$

考虑$x^m$项的系数，左边是$C_n^m$，右边是$C_k^aC_r^b$，得证。

实现：
上面的定理可以写成：

$$C_n^m\mod p=C_{\lfloor {n\over p}\rfloor}^{\lfloor {m\over p}\rfloor}\times C_{n\mod p}^{m\mod p}$$

对于左边的一部分递归至$m=0$，右边的一部分，预处理阶乘及其逆元，$n,m< p$，直接算就可以了。

ll get(ll n,ll m)
{
    return frc[n]*Inv[m]%mod*Inv[n-m]%mod;
}	
ll cal(ll n,ll m)
{
	if(m==0) return 1;
	return cal(n/mod,m/mod)*get(n%mod,m%mod)%mod;
}