[数据结构与算法]Acwing--885. 求组合数 I

给定 n 组询问，每组询问给定两个整数 a，b请你输出 Cbamod(109+7)的值。

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤10000
1≤b≤a≤2000

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

主要是用了一个公式，公式的来源有点类似于动态规划的思想，注意处理边界，即当j==0时表示从i个物品当中选0个物品的方案数为0,? c[i][j]=(c[i-1][j-1]+c[i-1][j]) 从i个苹果中挑选出j个苹果?即可以分为两个集合，包含金苹果的? ?和不含金苹果的 ，那么包含金苹果的集合就是?c[i-1][j-1]? ?即再从i-1个苹果中挑选 j-1 个苹果? ,不含金苹果的集合就是?c[i-1][j]? ? 即从i-1个苹果中挑选出 j个苹果。🏁🏁🏁🐳🐳

#include<bits/stdc++.h>
using namespace std;
int c[2020][2020];
int mod=1e9+7;

void init()
{
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)c[i][j]=1;
            else
            {
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
            }
        }
    }
}

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