算法

题型:给定两个正整数a与b,求Cbamod(1e9+7)Cabmod(1e9+7)
递推式:
Cba=Cb−1a−1+Cba−1
Cab=Ca−1b−1+Ca−1b
解析:

CbaCab的含义就是可以理解成从Acwing网站中a位巨佬中选出b位巨佬的总方案数
a位巨佬中抽出b位巨佬的方案数 可以 分为两类
1.情况①:选抽风抽风巨佬
那么此时已经选出了一位抽风抽风巨佬,剩下只要从a-1位巨佬中选出b-1位巨佬
2.情况②:不选抽风抽风巨佬
那么此时情况显然就是从剩下a-1位巨佬中选出b位巨佬
根据加法计数原理有:
Cba=Cb−1a−1+Cba−1

// c[a][b] 表示从a个苹果中选b个的方案数
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;

C++ 代码

#include<iostream>
using namespace std;
const int mod = 1e9+7;
long long f[2010][2010];
int main()
{
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) f[i][j]=1;
            else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
        }
    }
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        printf("%ld\n",f[a][b]);
    }
}