题解 | 【模板】组合数

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 1e6 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il ll quick_mi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

il ll C(int n,int m,const vector<ll>&fact,const vector<ll>&invfact){
    if(m>n||m<0)return 0;
    return fact[n]*invfact[m]%mod*invfact[n-m]%mod;
}

il void solve(){    
    vector<ll>fact(5e5+5),invfact(5e5+5);
    fact[0]=1;
    for(int i=1;i<=5e5;i++){
        fact[i]=fact[i-1]*i%mod;
    }
    invfact[5e5]=quick_mi(fact[5e5],mod-2);
    for(int i=5e5-1;i>=0;i--){
        invfact[i]=invfact[i+1]*(i+1)%mod;
    }
    int q;
    cin>>q;
    while(q--){
        int n,m;
        cin>>n>>m;
        cout<<C(m,n,fact,invfact)<<'\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    // cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}