求组合数 I(数据量a<=2000,b<=2000,递推的方法)

• 性质1：$C_{a}^{0}=1$
• 性质2：$C_{a}^{b}= C_{a-1}^{b-1}+C_{a-1}^{b}$

性质2的证明(有点像01背包)

• $C_{a}^{b}$表示为在a个数里挑b个数的方案数
• 那么从第i个数去考虑,分为两种情况选第i个数和不选第i个数
• 情况1选第i个数：那么剩下b-1个数就在a-1个数里面选,即$C_{a-1}^{b-1}$
• 情况2不选第i个数：那么剩下b个数就在a-1个数里面选,即$C_{a-1}^{b}$
• 情况1和情况2的方案数相加即为$C_{a}^{b}$的方案数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2010,mod=1e9+7;
int c[N][N];
int n;

void init()//预处理所有的组合数,时间复杂度在4*10^6
{
    for(int i=0;i<N;i++)//坑点：不能写成i<=N,不然会数组越界
        for(int j=0;j<=i;j++)
        {
            if(!j) c[i][j]=1;//这就是定义c[i][0]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//有点像01背包思想
        }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    init();
    while (n -- )
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]%mod<<endl;
    }

}