题解 | 【模板】组合数

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
using ll = long long;
using vl = vector<ll>;
const ll mod = 1000000007;

ll ksm(ll x, ll n) {//快速幂
    ll ans = 1;
    while (n > 0) {
        if (n & 1) {
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
ll ny(ll x) {//快速幂求逆元
    return ksm(x, mod - 2);
}
vl jcb, jcnyb;
void initjc(ll n) {//初始化阶乘表和阶乘逆元表
    jcb.assign(n + 1, 1);
    jcnyb.assign(n + 1, 1);
    for (ll i = 1; i <= n; ++i) {
        jcb[i] = jcb[i - 1] * i % mod;
    }
    jcnyb[n] = ny(jcb[n]);
    for (ll i = n - 1; i >= 0; --i) {
        jcnyb[i] = jcnyb[i + 1] * (i + 1) % mod;
    }
}
inline ll C(ll n, ll k) {//组合数公式
    if (k < 0 || k > n) return 0;
    return jcb[n] * jcnyb[k] % mod * jcnyb[n - k] % mod;
}

void solve() {
    int n, m;cin >> n >> m;
    cout << C(m, n) << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    initjc(5e5 + 10);
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

初始化阶乘表和阶乘逆元表，逆元要用到费马小定理和快速幂，带入组合数公式即可，注意这里模数一定要是质数才有意义。