卢卡斯定理

一、卢卡斯（Lucas）定理

求
$$C_n^m \ (\bmod \ p)$$

1.定理

$$ \begin{aligned} & a=a_kp^k+a_{k-1}p^{k-1}+\dots+a_1p+a_0 \\ & b=b_kp^k+b_{k-1}p^{k-1}+\dots+b_1p+b_0 \end{aligned} $$

其中 $0 \le a_i,b_i \le p-1$ 为整数， $i=1,2,\dots,k$
$$C_a^b \equiv C_{a_k}^{b_k} \cdot C_{a_{k-1}}^{b_{k-1}} \cdot \dots \cdot C_{a_0}^{b_0}\ (\bmod \ p)$$

2.证明

$\because$ $p$ 为素数
$\therefore$ 对于 $1 \le i \le p-1$ ，有 $$C_p^i=\frac{p}{i} C_{p-1}^{i-1} \equiv 0 \ (\bmod \ p)$$
由二项式定理
$$(1+x)^p=\sum\limits_{i=0}^p C_p^ix^i \equiv 1+x^p \ (\bmod \ p)$$
由算术基本定理
$$(1+x)^a=\prod\limits_{i=0}^p ((1+x)^{p^i})^{a_i} \equiv \prod\limits_{i=0}^p (1+x^{p^i})^{a_i} \ (\bmod \ p)$$
由二项式定理，对比系数得
$$C_a^b \equiv C_{a_k}^{b_k} \cdot C_{a_{k-1}}^{b_{k-1}} \cdot \dots \cdot C_{a_0}^{b_0}\ (\bmod \ p)$$

int fac[N];
inline int Pow(int a,int b,int p){
    int res=1;
    for(b%=p;b;b>>=1){
        if(b&1)
            (res*=a)%=p;
        (a*=a)%=p;
    }
    return res;
}
inline int C(int n,int m,int p){
    if(n<m)
        return 0;
    return ((fac[n]*Pow(fac[m],p-2,p))%p*Pow(fac[n-m],p-2,p)%p)%p;
}
int Lucas(int n,int m,int p){
    if(m==0)
        return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
inline void calcFac(int p){
    fac[0]=1;
    for(int i=1;i<=p;i++)
        fac[i]=(fac[i-1]*i)%p;
}