Find the combination number acwing 887 Find combination number III

Find the combination number AcWing 887. Find the combination number III

Original link

AcWing 887. Find the combination number III

Algorithm tags

Combinatorial mathematics Combination count Lucas Theorem Inverse element Fast power Fermat's small Theorem

Ideas

Code

#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105;
double a[N][N], eps = 1e-8;
int n;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
int qmi(int a, int b, int p){
    int ans=1;
    while(b){
        if(b&1){
            ans=ans*a%p;    
        }
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int C(int a, int b, int p){
    if(a<b){
        return 0;
    }else{
        int res=1;
        // for The loop only executes b Time , So it's from a Start riding b Number , namely a*(a-1)*…*(a-b+1), That's equal to a!/(a-b)!
        for(int i=1, j=a; i<=b; ++i, --j){
            res=res*j%p;
            res=res*qmi(i, p-2, p)%p;
        }
        return res;
    }
}
int lu(int a, int b, int p){
    if(a<p&&b<p){
        return C(a, b, p);
    }else{
        return C(a%p, b%p, p)*lu(a/p, b/p, p)%p;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n=read();
    while(n--){
        int a=read(), b=read(), p=read();
        printf("%lld\n", lu(a, b, p));
    }
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support