快速幂求逆元-组合数-费马小定理

重点
1. 快速米求逆元的公式推导-费马小定理
2. 递推公式fact和infact的确定
3. 注意整数溢出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N = 100010, M = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int k, int p) {  //快速米求逆元
    int res = 1;
    while (k) {
        if (k & 1) res = (LL) res * a % p;
        a = (LL) a * a % p;
        k >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    fact[0] = 1, infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (LL) fact[i - 1] * i % M;
        infact[i] = (LL) infact[i - 1] * qmi(i, M - 2, M) % M; 
    }
    while (n--) {
        int a, b;
        cin >> a >> b;
        cout << ((LL) fact[a] * infact[a - b] % M) * infact[b] % M << endl; 
    }

    return 0;
}