Lucas定理模板

Lucas定理：

Lucas定理是用来求 C(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;

简单的理解就是：

以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于

划归了一个子问题，这样递归求解即可。

这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（ｎ－ｍ）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了

Lucas最大的数据处理能力是p在10^5左右。

而C(a,b) =a! / ( b! * (a-b)! ) mod p

其实就是求 ( a! / (a-b)!)  * ( b! )^(p-2) mod p

(上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1,

那么a和a^(p-2)互为乘法逆元，则（b / a) = (b * a^(p-2) ) mod p)

ll quick_pow(ll a,ll n,ll p)
{
ll x = a;
ll res = 1;
while(n)
{
if(n & 1)
{
res = ((ll)res * (ll)x) % p;
}
n >>= 1;
x = ((ll)x*(ll)x) % p;
}
return res;
}

ll C(ll n,ll m,ll p)
{
ll a = 1,b = 1;
if(m > n) return 0;
//实现(a!/(a-b)!) * (b!)^(p-2)) mod p
while(m)
{
a = (a * n) % p;
b = (b * m) % p;
m--;
n--;
}
return ((ll)a * (ll)quick_pow(b,p-2,p))%p;
}

ll Lucas(ll n,ll m,ll p)
{
if(m==0)
return 1;
return((ll)C(n%p,m%p,p)*(ll)Lucas(n/p,m/p,p))%p;
}