当前位置：首页 > news >正文

题解：AcWing 885 求组合数I

news 2026/6/22 22:58:31

【题目来源】

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

【题目描述】

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

【输入】

第一行包含整数 $n$。

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

【输出】

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

【输入样例】

【输出样例】

3
10
1

【核心思想】

问题分析：给定 $n$ 组询问，每组询问给定两个整数 $a, b$，要求计算组合数 $C_a^b \bmod (10^9+7)$ 的值。这是一个经典的组合计数问题，数据范围较小（$a \leq 2000$），适合使用递推预处理的方法在 $O(N^2)$ 时间内预计算出所有组合数，之后每次查询 $O(1)$ 输出。
算法选择：
- 递推法（杨辉三角）：利用组合数的递推关系 $C(n, k) = C(n-1, k) + C(n-1, k-1)$，从边界情况出发逐步填表
- 动态规划思想：将问题分解为子问题，每个组合数依赖于上方和左上方的两个值，避免重复计算
- 模运算：每一步计算都对 $10^9+7$ 取模，防止整数溢出
关键步骤：
- 预处理组合数表：
  - 初始化二维数组 c[N][N]，其中 c[i][j] 表示 $C_i^j \bmod (10^9+7)$
  - 边界条件：对于所有 $i \in [0, N)$，`c[i][0] = 1$（$C_i^0 = 1$）
  - 递推填表：对于 $i$ 从 $0$ 到 $N-1$，$j$ 从 $1$ 到 $i$：
    - c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
  - 总预处理时间 $O(N^2)$，其中 $N = 2005$
- 处理查询：
  - 读取询问组数 $n$
  - 对于每组询问 $(a, b)$：
    - 直接查表输出 c[a][b]
  - 单次查询时间 $O(1)$
时间/空间复杂度：
- 时间复杂度：$O(N^2 + n)$，预处理 $O(N^2)$（$N = 2000$），每次查询 $O(1)$
- 空间复杂度：$O(N^2)$，存储组合数表 c[N][N]
递推法求组合数的核心思想：
- 递推公式来源：从 $n$ 个元素中选 $k$ 个，考虑第 $n$ 个元素：若选，则需从前 $n-1$ 个中选 $k-1$ 个（$C(n-1, k-1)$）；若不选，则需从前 $n-1$ 个中选 $k$ 个（$C(n-1, k)$）。故 $C(n, k) = C(n-1, k) + C(n-1, k-1)$
- 与杨辉三角的关系：组合数表就是杨辉三角，每个数等于上方两数之和
- 预处理策略：当查询次数多而数据范围不大时，预处理所有组合数并查表，比每次用阶乘+逆元计算更高效
- 取模处理：加法取模可在每次加法后立即进行，避免中间结果溢出
- 适用于 $n$ 较小（通常 $n \leq 2000$）且查询次数多的组合数计算场景

【解题思路】

【算法标签】

排列组合

【代码详解】

#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; // 程序结束
}

#include <bits/stdc++.h>
using namespace std;const int N = 2005;         // 最大n值
const int mod = 1e9 + 7;    // 模数，用于防止溢出int c[N][N];  // 组合数表，c[n][k] 表示 C(n, k) mod mod// 初始化组合数表（递推法）
void init()
{for (int i = 0; i < N; i++)  // 遍历所有n{for (int j = 0; j <= i; j++)  // 对于每个n，遍历所有k (0 ≤ k ≤ n){if (!j)  // 基本情况1：C(n, 0) = 1{c[i][j] = 1;}else{// 递推公式：C(n, k) = C(n-1, k) + C(n-1, k-1)c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}}}
}int main()
{// 预处理组合数表init();int n;  // 查询次数cin >> n;while (n--)  // 处理每个查询{int a, b;  // 输入n和kcin >> a >> b;// 直接查表输出组合数cout << c[a][b] << endl;}return 0;
}

【运行结果】