定义

从$n$个不同元素中，任取$m(m≤n)$个元素并成一组，叫做从$n$个不同元素中取出$m$个元素的一个组合；从$n$个不同元素中取出$m(m≤n)$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数。

计算公式:

$$ C_a^b = \cfrac{a!}{(a-b)!b!} $$

求法$first$

(求组合数 I)
数据范围：
$1≤n≤10000,$
$1≤b≤a≤2000$

预处理(递推式):

思想: $ \color{red}{递推} $
$$ C_a^b = C_{a-1}^b + C_{a-1}^{b-1} $$

解释：

如果从a个苹果中选出b个,那么情况大致可以分为两大类：
1. 选某一个苹果的组合,即$ C_{a-1}^{b-1}$
2. 选除这一个以外的苹果的组合,即$ C_{a-1}^b $

总共个数即为$ C_a^b = C_{a-1}^b + C_{a-1}^{b-1} $

C++代码：

#include <iostream>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init()  // 预处理
{
    for (int i = 0; i < N; i ++)
        for (int j = 0; j <= i; j ++)
        {
            if(i == j) c[i][j] = 1;       // 特判边界
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;  // 代入公式
        }
}
int main()
{
    init();
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

求法$second$

(求组合数 II)
数据范围:
$1≤n≤10000,$
$1≤b≤a≤10^5$

预处理:

思想:$ \color{red}{用快速幂来求逆元 + 递推} $
先要预处理出来 $ a! $ 以及 $ (a-b) $和$ b! $的逆元
如果$fact[i]=i!$ $ mod $ $ 10^9+7$
$infact[i]={i!}^{-1}$ $ mod $ $ 10^9+7$
那么$C_a^b=fact[a]$ × $infact[a-b]$ × $infact[b]$
注意:$\cfrac{a}{b}$ $mod\space p$ $\not=$ $ \cfrac{a \space mod \space p}{b \space mod \space p} $

C++代码

#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 % p;
    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;    // 预处理出 a!
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; // 预处理出 (a-b)! 和 b! 的逆元
    }
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod); // 预处理之后计算出组合数并输出
    }
    return 0;
}