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

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;  
}