【模板】Lucas定理

若 \(p\) 为质数，则对于任意整数 \(1\le m \le n\)，有：

\(C_n^m \equiv C_{n \div p}^{m \div p} \times C_{n\mod p}^{m\mod p} (mod~p)\)

也就是把 \(n\) 和 \(m\) 表示成 \(p\) 进制数，并且对 \(p\) 进制数下的每一位分别计算组合数，累乘起来。

CODE

inline int power(int x,int y,int p){
    int res=1;
    while(y){
        if(y&1) res=res*x%p; 
        x=x*x%p; 
        y>>=1;
    }
    return res%p;
}
inline int C(int x,int y,int p){
	if(y>x) return 0;
	return jc[x]*power(jc[y]*jc[x-y]%p,p-2,p)%p;//乘上逆元
}
inline int Lucas(int x,int y,int p){
    if(!y) return 1;
    return C(x%p,y%p,p)*Lucas(x/p,y/p,p)%p;
}