[AcWing]885. 求组合数 I（C++实现）求组合数第一种题型模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

求组合数有很多种题型，我们需要根据输入的数据的范围来选哪种方式，具体的方式有如下几种：
主要是询问次数和数据大小的不同，对应了不同的解法
此外，另有高精度组合数和卡特兰数两种特例

1. 题目

2. 读题（需要重点注意的东西）

思路：

首先，要知道组合数是什么？公式是什么？
一般地，从a个不同的元素中，任取b（b≤a）个元素为一组，叫作从aa个不同元素中取出b个元素的一个组合，这个组合一共有多少组？
公式如下：

可以推出
（先取出1个元素，这个元素可能在b中，可能不在，所以有如下两种可能）

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <iostream> #include <algorithm>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; // 如果j为0else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; }int main() {int n;init();scanf("%d", &n);while (n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", c[a][b]);}return 0; }

---

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

• 组合数

6. 总结

求组合数第一种题型的模板题，理解思路并背下代码。

总结

以上是生活随笔为你收集整理的[AcWing]885. 求组合数 I（C++实现）求组合数模板题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。