如何计算组合数C(n, m)？
摘要：71.Acwing基础课第885题-简单-求组合数 I 题目描述 (给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C^b_amod(10^9+7)的值)。 输入格式 (第一行包含整数 n)。 (接下来
71.Acwing基础课第885题-简单-求组合数 I
题目描述
\(给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C^b_amod(10^9+7)的值\)。
输入格式
\(第一行包含整数 n\)。
\(接下来 n 行，每行包含一组 a 和 b\)。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
\(1≤n≤10000\)，
\(1≤b≤a≤2000\)
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
代码：
// 包含基础输入输出、算法头文件
#include <iostream>
#include <algorithm>
using namespace std;
// 常量定义：
// N=2010：预处理组合数的最大范围（支持C(a,b)中a≤2000）
// mod=1e9+7：模数（防止组合数溢出，符合竞赛常用模数要求）
const int N = 2010, mod = 1e9 + 7;
// 组合数数组：c[i][j] 表示 C(i,j)（从i个元素中选j个的组合数）
int c[N][N];
// 预处理函数：用杨辉三角公式初始化所有C(i,j)，时间复杂度O(N²)
void init()
{
// 遍历所有可能的i（总数）
for (int i = 0; i < N; i ++ )
// 遍历j（选取数），j≤i（选的数不能超过总数）
for (int j = 0; j <= i; j ++ )
// 组合数边界条件：C(i,0)=1（从i个中选0个，只有1种选法）
if (!j) c[i][j] = 1;
// 杨辉三角核心递推公式：C(i,j) = C(i-1,j) + C(i-1,j-1)
// 取模：防止数值溢出，且符合模运算性质
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main()
{
int n; // n：查询的组数
// 先预处理所有组合数（仅需初始化一次，多次查询直接查表）
init();
// 输入查询组数
scanf("%d", &n);
// 处理每组查询
while (n -- )
{
int a, b; // a：总数；b：选取数（查询C(a,b)）
scanf("%d%d", &a, &b);
// 直接输出预处理好的组合数（O(1)查询）
printf("%d\n", c[a][b]);
}
return 0;
}