组合数1

• $C_{a}^{b}=C_{a-1}^{b}+C_{a-1}^{b-1}$ 这个等式成立的原因是 $C^b_a$ 表示从 $a$个苹果中取出 $b$ 个苹果。 我们可以将其分为两大类。假定 $b$ 个苹果中有一个 特殊的红苹果 ， $C_a^b$ 可以分为①包含这个苹果，那么就是从 a - 1 个苹果里面选 b - 1 个苹果，是 $C_{b-1}^{a-1}$ ②不包含这个苹果，那么我要从除了这个苹果之外剩下的 a - 1 个苹果里面选出 b 个苹果，是 $C_{a-1}^{b}$ 。因此这个等式成立。
• 如果把数据预处理一遍可以降低时间复杂度，那么我们就要这样做。

组合数2

• 还是上一题的思想，如果能够通过预处理降低时间复杂度，我们就要这样做。这里因为 a! / (b! * (a - b)!) 等价于 a! * infact[b] * infact[a - b] （通过逆元把除法转换为乘法），所以我们可以通过先预处理出阶乘和逆元，然后通过查表每次 0(1) 地算出组合数的结果。
• 代码如下

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

const long long N = 1E5 + 10, MOD = 1E9 + 7;

long long fact[N];
long long infact[N]; // 逆元

long long ksm(long long a, long long b, long long p)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % p;
        }
        b >>= 1;
        a = a * a % p;
    }

    return res;
}

int main()
{
    // 初始化
    fact[0] = infact[0] = 1;
    for (long long i = 1; i <= N; i ++ )
    {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = ksm(fact[i], MOD - 2, MOD) % MOD;
    }

    long long T;
    cin >> T;
    while (T -- )
    {
        long long a, b;
        cin >> a >> b;
        // a! / (b! * (a - b)!) 等价于 a! * infact[b] * infact[a - b]
        cout << fact[a] * infact[b] % MOD * infact[a - b] % MOD << endl;
    }

    return 0;
}