求组合数有许多种不同的算法，要根据不同的数据量大小选择不同的算法

类型1

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

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

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

类型1思路

此时的参数为

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

这个例子的n很大，a,b很小，所以我们可以预处理出所有的c（a b）组合数，利用DP的思想

c（a b）可以看作是从a个苹果中选取b个苹果，

若首先选择选择一个苹果，则组合数可拆分为两种情况

包含该苹果或不包含该苹果，刚好涵盖了所有情况 

 类型1代码

#include<iostream>

using namespace std;

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

void init()
{
	for(int i = 0; i < N; 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 main()
{
	init();
	
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		cout << f[a][b] << endl;
	}
	
	return 0;
} 

 类型2

数据范围类型：

1≤n≤100001≤n≤10000,
1≤b≤a≤105

类型2思路

 a,b数据也较大，先预处理出各个数的阶乘，然后再模拟手工计算，利用公式算出结果。

由于结果中有除法，且为大数，可能会有溢出，因此这里用了逆元，逆元可以用快速幂来算。

类型2代码

#include<iostream>

using namespace std;

typedef long long LL;
int p = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N], infact[N];//阶乘和逆
 
int qmi(int a, int k, int p)
{
	int res = 1;
	while(k)
	{
		if(k & 1) res = (LL) res * a % p;
		a = (LL) a * a % p;
		k >>= 1;
	}
	
	return res;
}

int main()
{
	int n;
	cin >> n;
	
	fact[0] = infact[0] = 1;
	for(int i = 1; i < N; i ++)
	{
		fact[i] = (LL) fact[i - 1] * i % p;
		infact[i] = (LL) infact[i - 1] * qmi(i, p - 2, p) % p;
	}
	
	while(n --)
	{
		int a, b;
		cin >> a >> b;	
		int res;
		res = (LL) fact[a] * infact[b] % p * infact[a - b] % p;
		cout << res << endl;
	}
	
	return 0;
}