887. 求组合数 III

#include<bits/stdc++.h>

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

第一个求组合数是使用类似于动态规划来求解

第二个求组合数是使用逆元来求解

第三个求组合数是使用卢卡斯定理来求解

卢卡斯定理如下

具体的数学证明稍作了解即可，主要是记住公式加上用代码模拟公式

快速幂是用来求逆元的，第二个函数是模拟这个公式

因为要取模，所以不可以直接除，使用逆元，然后是代码模拟实现卢卡斯定理，最后查询即可

以上