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

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

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

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

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

数据范围
1≤n≤10000,
1≤b≤a≤2000

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

题目分析：
根据加法计数原理有：
C^b_a=C^b−1_a−1+C^b_a−1
所以可以先预处理，然后直接查表即可

#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++) // 不能相等 N 超界
        for(int j=0;j<=i;j++)
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27