Lucas定理

对于C(m,n)%P(P是质数)这样的问题,可以通过预处理阶乘和阶乘的逆元,来快速计算。但是当m,n大于P时,就不能保证m,n与P互质了,但不互质的情况下,乘法逆元不存在,此时就需要卢卡斯定理来减小m,n的规模,此处证明略去,给出公式:
C(n,m)%P=C(n/P,m/P)*C(n%P,m%P)%P
```C++
ll Lucas(ll n,ll m)
{
if (m==0)
return 1;
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
```

05-27 21:10