莫欺少年穷，修仙之旅在这开始—>算法基础课题解

重要公式： $C_a^b=C_{a-1}^{b-1}+C_{a-1}^b$

证明：

1. 若选择第 b 个物品，则需要在剩下 a-1 个物品中选择 b-1 个物品，组合数为 $C_{a-1}^{b-1}$
2. 若不选择第 b 个物品，则需要在剩下 a-1 个物品中选择 b 个物品，组合数为 $C_{a-1}^b$
3. 将两者相加，即 $C_a^b=C_{a-1}^{b-1}+C_{a-1}^b$

本题思路： 由于数据范围为 $1\le b\le a\le 2000$，共 4000000 种组合，故可先预处理再查表

代码如下

#include<bits/stdc++.h>

using namespace std;

const int N = 2010, mod = 1e9 + 7;

int n;
int c[N][N];

//预处理，用于查表
void init()
{
    for(int i=0;i<N;i++)
        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();

    cin>>n;

    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }

    return 0;
}