lucas 定理，組合數取模

Lucas 定理求 Cmn%p 的值，如果n，m的值過大，不易直接求出，是以利用lucas定理

定理 Cmn%p =Cm/pn/p∗ Cm%pn%p

證明：百度百科

預備知識①   Cip%p=0 p 為素數且， i≠p and i≠0

預備知識②   二項式定理:  

特殊情況 當 a=1,b=x

(1+x)n=∑i=0nCinxi

證明如下

n = sp + q;

m = tp + r;

（1+x)n=(1+x)sp+q≡(1+x)sp∗(1+x)q≡(1+xp)s∗(1+x)q−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− (①)

≡∑i=0sCis∗xp∗i∗∑j=0qCjqxj (②)

{直接展開即可獲得}

又知 (1+x)n=∑i=0nCin∗xi

求等式兩邊 xtp+r 的系數

left=Cmn

right=Cts∗Crq (隻有當i = t，j = r的時候才有 xtp+r 的系數

于是問題得證

代碼參考

long long qpow(long long a,long long b,long long m)
{
 long long ans = ;
 a %= m;
 while(b>)
 {
     if(b&)
     ans = ans*a%m;
     a = a*a%m;
     b >>= ;
 }
    return ans;
}
long long  C(long long  n,long long m,long long p)
{
    if(m>n)
        return ;
    long long tmp1 = ,tmp2 = ;
    for(long long i = n-m+;i <= n; ++i)
       {
            tmp1 = tmp1*i % p;
            tmp2 = tmp2 *(n-i+) %p;
       }
    return  tmp1*qpow(tmp2,p-,p)%p;
}
int lucas(int n,int m,int p)
{
    if(m==)
        return ;
    return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}