Lucas 定理
[C_m^n equiv C_{m mod p}^{n mod p} C_{lfloor frac{m}{p}
floor}^{lfloor frac{n}{p}
floor} pmod{p}
]
证明
规定：(inv_x) 表示 (x) 在模 (p) 意义下的逆元
(C_p^x equiv p cdot inv_x cdot C_{p-1}^{x-1} pmod{p})
这里 (0 < x <p)
[C_p^x = frac{p!}{x!(p-x)!} = frac{p cdot (p-1)!}{x cdot (x-1)!(p-x)!} = frac{p}{x} cdot frac{(p-1)!}{(x-1)![(p-1)-(x-1)]} = frac{p}{x} cdot C_{p-1}^{x-1} equiv p cdot inv_x cdot C_{p-1}^{x-1} pmod{p}
]
((1+x)^p equiv 1 + x^p)
根据二项式定理：
[(1+x)^p = sumlimits_{i=0}^p C_p^i cdot x^i cdot 1^{p-i}
]
[= sumlimits_{i=0}^p C_p^i cdot x^i
]
(ecause C_p^x equiv p cdot inv_x cdot C_{p-1}^{x-1} equiv 0 pmod{p})
[ herefore (1+x)^p = C_p^0 cdot x^0 + C_p^p cdot x^p
]
[= 1 + x^p
]
推 式 子
设 (left{ egin{matrix} s = lfloor frac{m}{p} floor \ r = m mod p \ end{matrix} ight.)，则 (m=sp+r)
[ecause (1+x)^m = sumlimits_{k=0}^{m} C_m^k x^k
]
[(1+x)^m = (1+x)^{sp+r} = (1+x)^{sp} cdot (1+x)^r
]
[= [(1+x)^p]^s cdot (1+x)^r
]
[equiv (1+x^p)^s cdot (1+x)^r pmod{p}
]
[= sumlimits_{i=0}^s C_s^i x^{ip} cdot sumlimits_{j=0}^r C_r^j x^j
]
[= sumlimits_{i=0}^s sumlimits_{j=0}^r C_s^i C_r^j x^{ip+j}
]
因为 (ip+j) 刚好会枚举到 ([0,m]) 中的整数各一次（对于每个在 ([0,m]) 中的整数 (x) 都可以拆成 (lfloor frac{x}{p} floor cdot p + x mod p)的形式，而 (i = lfloor frac{x}{p} floor,j = x mod p)），所以转而枚举 (k=ip+j)：
[(1+x)^m equiv sumlimits_{k=0}^m C_s^{lfloor frac{k}{p}
floor} C_r^{k mod p} pmod{p}
]
让 (k=n)，则
[C_m^n equiv C_s^{lfloor frac{n}{p}
floor} C_r^{n mod p} = C_{m mod p}^{n mod p} C_{lfloor frac{m}{p}
floor}^{lfloor frac{n}{p}
floor} pmod{p}
]
得证.
代码实现
如果寻求高效率，建议先预处理出 (0)~(p) 在模 (p) 意义下的逆元和 (0)~(p) 的阶乘：
for(int i=2;i<=p;i++)
{
fac[i]=1ll*fac[i-1]*i%p;
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
}
然后再处理出 (0)~(p) 的阶乘的逆元：
for(int i=2;i<=p;i++)
inv[i]=1ll*inv[i-1]*inv[i]%p;
//注意不能和求0~p的逆元放一起做！！！
然后就是快快乐乐的 (Lucas) 了：
int C(int _m,int _n,int mod)
{
if(_n>_m) return 0;
return 1ll*fac[_m]*inv[_n]%mod*inv[_m-_n]%mod;
}
int Lucas(int _m,int _n,int mod)
{
if(_n==0){return 1;}
else return 1ll*C(_m%mod,_n%mod,mod)*Lucas(_m/mod,_n/mod,mod)%mod;
}