老样子，先介绍什么是组合数。

每次从$n$个不同的元素中选择$m$个不同的元素($0\le m \le n$)，将这$m$个元素合成一组而不考虑其顺序，我们将其称为从$n$个元素中不重复地选择$m$个元素的组合。所有这样的组合的总数称为组合数。

组合数的计算公式如下：
$$C_n^m = \frac{n!}{m! \times (n-m)!} = \frac{n\times (n-1)\times\cdots\times (n-m+1)}{m!},C_n^0 = 1;$$

下面就是求解组合数的四种方法，这四种方法各有优势，它们分别应用在不同的场景中。

递推法求组合数

递推，故名思意，就是通过已有的组合数来得到当前的组合数。具体而言，$C_a^b = C_{a-1}^{b-1} + C_{a-1}^{b}$。

通俗地理解，假如有$a$个苹果，我们可以将这$a$个苹果分为两堆，其中一堆有$a-1$个苹果，而另一堆只有1个苹果。从这$a$个苹果里选择$b$个苹果有两种选法，一种是选法包括只有1个苹果的一堆，而另一种选法不包括1个苹果一堆，这两种选法分别有$C_{a-1}^{b-1}$和$C_{a-1}^{b}$种。

时间复杂度及其应用

时间复杂度：$O(N^2)$
应用：由于采用的是递推方式，而且算法的时间复杂度是二次阶，所以它仅适用于$a$较小的情况。

关键代码实现如下：

int C[N][N] = {};
const int mod = 1e9 + 7;
for(int i = 0;i < N; ++ i){
    for(int j = 0;j <= i; ++ j){
        if(j == 0) C[i][j] = 1;
        else C[i][j] = (long long)(C[i-1][j] + C[i-1][j-1])%mod;
    }
}

需要注意：$j \le i$，而且需要对$j = 0$的情况作单独处理。

需要预处理的乘法逆元求解组合数

当$a$比较大的时候，上述递推方法求解组合数不再适用，因此我们需要寻找新的快速求解组合数的方法。
在上面我提到了组合数的计算公式$C_n^m = \frac{n!}{m! \times (n-m)!}$，在模$p$($p$是质数)的情况下，有$C_n^m\; \%\; p= \frac{n!}{m! \times (n-m)!}\;\% \;p \equiv n! \times (m!)^{-1}\times ((n-m)!)^{-1}\; \% \;p$，其中，$(m!)^{-1}, ((n-m)!)^{-1}$分别表示在模$p$的情况下$m!$和$(n-m)!$的逆元。

因此，利用乘法逆元求解组合数的基本思路如下：
1. 首先预处理出所有的阶乘以及相应的乘法逆元(在模$p$的情况下)；
2.然后针对每一个询问，利用上述公式进行求解组合数。

算法时间复杂度及其应用

首先，我们要处理每一个数字的阶乘，需要对每一个数字进行遍历，所以这一步骤的时间复杂度是$O(N)$。
其次，我们还要处理每一个数字阶乘的逆元，在求解逆元时我们使用的算法时快速幂算法。由于快速幂算法的时间复杂度是$O(logN)$，所以这一步骤的时间复杂度是$O(logN)$
最后，算法的总时间复杂度是两个步骤时间复杂度的乘积，即$O(NlogN)$。
相比于递推法求解组合数，该算法时间复杂度更小，因此适合用于$a$较大的情况。

关键代码实现如下

const int mod = 1e9+7;
int fact[N],infact[N];//fact[i]用于存放i的阶乘，而infact[i]用于存放i阶乘的逆元

int qmi(int a,int b,int p){
    int res = 1;
    while(b){
        if(b & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}
fact[0] = 1,infact[0] = 1;//0的阶乘及其逆元都是1
for(int i = 1;i < N; ++ i){
    fact[i] = (long long)fact[i  - 1] * i % mod;
    infact[i] = qmi(fact[i],mod - 2,mod);//利用快速幂来求解乘法逆元
}

卢卡斯定理求解组合数

卢卡斯定理
卢卡斯定理用于求解大组合数取模的问题。
对于非负整数$n,m$和质数$p$，$C_n^m = \prod \limits_{i=0}^{k}C_{n_i}^{m_i} \;\%\;p$，其中，$m = m_kp^k+\cdots+m_1p + m_0$，$n = n_kp^k +\cdots n_1p + n_0$是$m$和$n$的$p$进制展开。但实际上我们常常用到的公式是$C_n^m \equiv C_{n\;mod\;p}^{m\;mod\;p}C_{n/p}^{m/p}$。

其中，$C_{n\;mod\;p}^{m\;mod\;p}$是利用乘法逆元来求解组合数，与上述使用预处理方式求解组合数的方法还是有些许不同的。
1.该方法不需要进行阶乘及其逆元的预处理
2.该方法使用的是求解组合数的第二个公式，即$C_n^m =\frac{n\times (n-1)\times\cdots\times (n-m+1)}{m!}$

算法的应用

该算法适用于$a$和$b$大于质数$p$的情况,而无论是递推方法求解组合数，还是预处理的乘法逆元方式求解组合数，都必须要求$a,b<p$

该算法的基本思路如下：
首先利用卢卡斯定理分解待求得组合数，接着计算$n\times (n-1)\times\cdots\times (n-m+1)$以及$m!$的结果，接着利用快速幂算法求解，最后计算结果。

关键代码实现

int qmi(int a,int b,int p){
    int res = 1;
    while(b){
        if(b & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}
int C(int a,int b,int p){
    if(b > a) return 0;
    int res = 1,inv = 1;
    for(int i = 1,j = a;i <= b;++i,--j){
        res =(long long)j * res % p;
        inv = (long long)i * inv % p;
    }
    inv = qmi(inv,p-2,p);
    return (long long)res * inv % p;
}
int lucas(long long a,long long b,int p){
    if(a < p && b < p) return C(a,b,p);
    else return (long long)C(a%p,b%p,p) * lucas(a/p,b/p,p)% p;
}

利用高精度求解组合数

在这种情况下，题目中并不要求组合数对一个数取模，这也就意味着我们不能够使用与同余相关的任何定理。
考虑到计算出来的组合数结果很大，会远远超出int整型所表示的范围。那么这时我们该如何处理？
注意到组合数的计算公式$C_n^m = \frac{n!}{m! \times (n-m)!} = \frac{n\times (n-1)\times\cdots\times (n-m+1)}{m!}$，我们想到利用高精度乘除法来求解组合数。( https://www.acwing.com/blog/content/21516/ )
如果直接利用高精度乘法和高精度除法求解组合数，虽然可以求解出来，但是效率很低。因此我们需要对数据进行一定地处理。

解题思路剖析

1.注意到组合数一定是一个整数，那么依据质因数分解定理，该组合数一定可以分解为若干个质因数的幂次的乘积。
2.接上一条，我们对组合数公式的分子和分母进行质因数分解，由于组合数一定是整数，那么分子中一定包含分母中所有的质因数，并且对于同一质因数，分子中的幂次一定大于等于分母中的幂次。
3.由上面两条可以得到，组合数的质因数以及其幂次可以由分子质因数分解与分母质因数分解的比值求得。
4.因此，我们可以分别求得分子和分母质因数分解的表达式，然后利用高精度乘法求解组合数。

代码实现思路

1.我们需要筛选出要题目所给范围的所有的质数，因此需要利用到筛质数算法(链接 https://www.acwing.com/blog/content/21714/ )
2.如何求解$n!$中某一质数$p$的幂次？这里有一个小技巧，我们可以利用$\frac{n}{p}+\frac{n}{p^2}+\cdots+\frac{n}{p^k}$来求解$p$的幂次。那么用这个式子求解合理吗？答案当然是合理的。

代码实现如下：

const int N = 5010;
int prime[N],cnt;
bool st[N];
vector<int> mul(vector<int> &v,int b){//高精度乘法
    vector<int> res;
    int t = 0;
    for(int i = 0;i < v.size() - 1;++ i){
        t += v[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }

    while(t){
        res.push_back(t % 10);
        t /= 10;
    }

    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

void getPrime(int x){//筛选质因数
    for(int i = 2;i <= x;++ i){
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0;prime[j] <= x/i; ++ j){
            st[prime[j] * i] = true;
            if(i % prime[j]) break;
        }
    }
}

int cnt(int n,int p){//统计n!中质数p的个数
    int res = 0;
    while(n){
        res += n/p;
        n /= p;
    }
    return res;
}

//计算组合数
void C(int a,int b){
    vector<int> res;
    res.push_back(1);
    for(int i = 0;i < cnt; ++ i){
        int p = prime[j];
        int ans = cnt(a,p) - cnt(b,p) - cnt(a - b,p);
        for(int j = 0;j < ans; ++ j){
            res = mul(res,p);
        }
    }

    //输出res
    for(int i = res.size() - 1;i >= 0;-- i){
        cout << res[i];
    }
}