lucas定理

卢卡斯定理 $Lucas Theory O(log_{p}Nplogp)$
acwing887求组合数3

$$C_{a}^{b} ≡ C_{amodp}^{bmodp}C_{\frac{b}{p}}^{\frac{a}{p}}(mod{~}p)\\\\ a=a_{k}p^{k}+a_{k-1}p^{k-1}+...+a_{0}p^{0}\\\\ b=b_{k}p^{k}+b_{k-1}p^{k-1}+...+b_{0}p^{0}--①\\\\$$ $$\begin{aligned} (1+x)^{p^{k}}&=C_{p}^{0} \times 1+C_{p}^{1} \times x+...+C_{p}^{p} \times x^{p}\\\\ (C_{p}^{1} \sim C_{p}^{p-1} mod p = 0)&=1+x^{p^{k}} (mod{~}p) \end{aligned}$$ $$\begin{aligned} (1+x)^{a}&=(1+x)^{a_{0}}((1+x)^{p})^{a_{1}}((1+x)^{p^{2}})^{a_{2}}...((1+x)^{p^{k}})^{a_{k}}\\\\ ((1+x)^{p^{k}}=1+x^{p} (modp))&=(1+x)^{a_{0}}(1+x^{p})^{a_{1}}(1+x^{p^{2}})^{a_{2}}...(1+x^{p^{k}})^{a_{k}} (modp)\\\\ &=C_{a_{0}}^{b_{0}} x^{b_{0}p^{0}}...C_{a_{k-1}}^{b_{k-1}}x^{b_{k-1} p^{k-1}}C_{a_{k}}^{b_{k}}x^{b_{k}p^{k}}+其他项\\\\ &=C_{a_{0}}^{b_{0}}... C_{a_{k-1}}^{b_{k-1}}C_{a_{k}}^{b_{k}} x^{b_{k}p^{k}+b_{k-1}p^{k-1}+...+b_{0}p^{0}}+其他项\\\\ (式①)&=C_{a_{0}}^{b_{0}}... C_{a_{k-1}}^{b_{k-1}}C_{a_{k}}^{b_{k}} x^{b}+其他项 \end{aligned}$$

∴有上式中等式左边$(1+x)^{a}$和右边的$x^{b}$的系数分别为:

$$C_{a}^{b} || C_{a_{0}}^{b_{0}}... C_{a_{k-1}}^{b_{k-1}}C_{a_{k}}^{b_{k}}(mod p)$$

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int qmi(int a,int k,int p)
{
    int res = 1;
    while(k)
    {
        if(k&1)res = (LL)res*a%p;
        a = (LL)a*a%p;
        k>>=1;
    }
    return res;
}

int C(int a,int b,int p)
{
    if(b>a)return 0;
    int res = 1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res = (LL)res*j%p;
        res = (LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
//对公式敲
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        LL a,b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a,b,p) << endl;
    }
    return 0;
}