题目描述

求组合数

C(a,b)表示从a中选b个数有多少种选法

C(a,b)=C(a-1,b)+C(a-1,b-1) 可看成一个矩阵，所求的位置等于上一行的两个位置相加

所以可以利用递增，从C(0,0)开始赋值

不从计算的角度，从选出次数多少的角度

C++ 代码

#include<iostream>
#include<algorithm>
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(!j)c[i][j]=1;   //只有一种选法，边界
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;  //防止溢出，%mod
        }
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}