Find the combination number AcWing 886. Find the combination number II

Original link

AcWing 886. Find the combination number II

Algorithm tags

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

Ideas

because (a / b) % p It's not equal to (a % p) / (b % p), So directly dividing by the corresponding factorial doesn't work , Requires factorial inverse elements

Code

#include<bits/stdc++.h>
#define int long long
#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 = 2005, mod = 1e9+7;
int f[N], fn[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;
}
void init(){
    f[0]=fn[0]=1;
    rep(i, 1, N){
        f[i]=f[i-1]*i%mod;
        //  Inverse element 
        fn[i]=fn[i-1]*qmi(i, mod-2, mod)%mod;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read();
    init();
    while(n--){
        int a=read(), b=read();
        printf("%lld\n", f[a]*fn[b]%mod*fn[a-b]%mod);
    }
    return 0;
}

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