数学知识：求组合数 II—求组合数

题目：AcWing 886. 求组合数 II
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C^b_amod(10⁹+7) 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤10⁵

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

题目分析：
该题是预处理阶乘
因为组合可以换成阶乘的形式

但是除法应该换成逆元，所以需要用到快速幂的知识求逆元。
最后fact[i]表示i的阶乘，infact[i]表示i的逆元
C_a^b=fact[a] * infact[a-b] * infact[b]

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 100010,mod=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()
{
    
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++) // 预处理
    {
    
        fact[i]=(LL)fact[i-1]*i%mod; // 阶乘
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod; // 阶乘的逆元
    }
    
    int n;
    cin>>n;
    while(n--)
    {
    
        int a,b;
        cin>>a>>b;
        cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
    return 0;
}