886. 求组合数 II

个人不是很理解y总逆元递推公式的代码，所以我按我的思路写了一个

#include<iostream>
using namespace std;

const int N = 100010, mod = 1e9 + 7;
typedef long long ll;

//快速幂
int qmi(int a, int b, int p)
{
    int ret = 1;
    for(; b; b >>= 1, a = (ll)a * a % p)
        if(b & 1) ret = (ll)ret * a % p;
    return ret;
}

int fac[N]; // fac[i] 表示 i!
int inv[N]; // inv[i] 表示 i! 模 mod的乘法逆元。

void init()
{
    fac[0] = inv[0] = 1;
    for(int i = 1; i < N; ++i)
    {
        // i! = (i-1)! * i
        fac[i] = (ll)i * fac[i - 1] % mod;  

        // 根据前面所学的快速幂求逆元，a模m的乘法逆元就是 a^(m-2) % m。(前提是m为质数，且a与m互质)
        // inv[i] 表示 i! 模 mod的乘法逆元。所以inv[i] = (i!)^(mod - 2) % mod 
        // 而fac[i] 就是 i!, 直接一步快速幂即可
        inv[i] = qmi(fac[i], mod - 2, mod);

        //补：mod=1e9+7, 是质数, 且fac[i] < mod, 所以fac[i]一定与mod互质，就可以用之前的模板了
    }
}

int main()
{
    init();
    int n, a, b;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d %d", &a, &b);
        printf("%lld\n", ((ll)fac[a] * inv[a - b] % mod) * inv[b] % mod);
    }
    return 0;
}