lucas定理

1.lucas定理的作用

lucas定理听起来很高级，实际上它只是用来求(c_n^m mod p)，其中(p)是一个素数

2.lucas定理的表达式

[C_n^m mod p=C_{n/p}^{m/p}*C_{nmod p}^{mmod p} mod p ]

3.实现方式

所以我们就可已用递归的方式求(C_n^m mod p)
代码：

int pow(int x,int n){
    int ret=1;
    while(n){
        if(n&1)
            ret=(ret*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return ret;
}
int C(int n,int m){
    return fac[n]*pow(fac[m],mod-2)%mod*pow(fac[n-m],mod-2)%mod;
}
int Lucas(int n,int m){
    if(n<m)return 0;
    if(n<mod and m<mod)return C(n,m);
    return Lucas(n/mod,m/mod)*Lucas(n%mod,m%mod)%mod;
}