题解：AcWing 885 求组合数 I

【题目来源】

AcWing：885. 求组合数 I - AcWing题库

【题目描述】

给定 \(n\) 组询问，每组询问给定两个整数 \(a,b\)，请你输出 \(C_a^b\ mod\ (10^9+7)\) 的值。

【输入】

第一行包含整数 \(n\)。

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

【输出】

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

【输入样例】

3
3 1
5 3
2 2

【输出样例】

3
10
1

【解题思路】

【算法标签】

《AcWing 885 求组合数I》 #组合数学# #组合计数# #递推#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 2005, mod = 1e9 + 7; // 定义常量 N 和 mod
int c[N][N]; // c 数组存储组合数 C(i, j)// 初始化组合数表
void init()
{for (int i = 0; i < N; i++) { // 遍历 i 从 0 到 N-1for (int j = 0; j <= i; j++) { // 遍历 j 从 0 到 iif (j == 0) c[i][j] = 1; // 如果 j 为 0，C(i, 0) = 1else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; // 递推计算 C(i, j)}}
}int main()
{int n; // 定义整数 n，表示查询的次数init(); // 初始化组合数表cin >> n; // 输入查询的次数 nwhile (n--) { // 遍历每个查询int a, b; // 定义整数 a 和 bcin >> a >> b; // 输入 a 和 bcout << c[a][b] << endl; // 输出组合数 C(a, b)}return 0; // 程序结束
}

【运行结果】

3
3 1
3
5 3
10
2 2
1