AcWing 886. 求组合数 II

AcWing 886. 求组合数 II

费马小定理 和 乘法逆元

#include<bits/stdc++.h>

using LL = long long;
using namespace std;

const int mod = 1e9 + 7;
const int N = 100010;
LL fact[N], infact[N];

int qmi(LL a, LL b, LL mod) {
    LL res = 1;
    while (b) {
        if (b & 1)res = (LL) res * a % mod;
        b >>= 1;
        a = (LL) a * a % mod;
    }
    return res;
}

int main() {
    int n;
    int a, b;
    cin >> n;
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    
    while (n--) {
        cin >> a >> b;
         // 三个数相乘可能会溢出，所以中间还要mod一下
        LL res = fact[a] * infact[b] % mod * infact[a - b] % mod ; 
        cout << res << endl;
    }

    return 0;
}