预处理求组合数
预处理出C$_{a}^{b}$的所有情况
利用地推公式:Cab=Ca-1b+ca-1b-1;
算法1
C++ 代码
#include<bits/stdc++.h>
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;//从i个苹果选一个苹果
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main()
{
init();
int n;
scanf("%d",&n);
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",c[a][b]);
}
return 0;
}