第 25 章组合计数进阶 · 知识细节练习

壹

容斥原理

6 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

容斥原理两集合形式是？

（1 分）

A

$|A \cup B| = |A| + |B| - |A \cap B|$

B

$|A \cup B| = |A| + |B|$

C

$|A \cup B| = |A| \times |B|$

D

$|A \cup B| = |A| - |B|$

第 2 题 A2 未作答

容斥原理三集合形式是？

（1 分）

A

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

B

$|A| + |B| + |C|$

C

$|A| + |B| + |C| + |A \cap B \cap C|$

D

$|A| \times |B| \times |C|$

第 3 题 A3 未作答

判断题：容斥的补集视角 = 求"至少满足一个性质"用并集容斥；求"一个都不满足"用总数减去并集——两者互补。

（1 分）

A

正确

B

错误

第 4 题 A4 未作答

容斥原理最适合的计数场景是？

（1 分）

A

计数对象满足若干性质中的至少一个（性质有重叠）

B

计数完全互斥的分类

C

排序

D

求最短路

第 5 题 A5 未作答

判断题：容斥原理本质是集合运算的计数版——并集大小 = 各集合大小经"加奇减偶"（单项加、交集减、三重交集加…）修正。

（1 分）

A

正确

B

错误

第 6 题 A6 未作答

判断题：容斥的直观 = 先加起来（算重了）再减去重叠、加回三重重叠…——"加多了减、减多了加"。

（1 分）

A

正确

B

错误

贰

容斥应用

7 QUESTIONS · 2 POINTS EACH

第 7 题 B1 未作答

$1 \sim 100$ 中被 2 整除的数有 $50$ 个、被 3 整除的有 $33$ 个、被 6 整除的有 $16$ 个——被 2 或 3 整除的有多少个？

（1 分）

A

$67$ （ $50 + 33 - 16$ ）

B

$83$

C

$50$

D

$33$

第 8 题 B2 未作答

班级 50 人：会 C++ 的 30 人、会 Python 的 25 人、两样都会的 10 人——至少会一样的有多少人？

（1 分）

A

$45$ （ $30 + 25 - 10$ ）

B

$55$

C

$40$

D

$50$

第 9 题 B3 未作答

$|A| = 30$ 、 $|B| = 25$ 、 $|C| = 20$ 、 $|A \cap B| = 10$ 、 $|A \cap C| = 8$ 、 $|B \cap C| = 6$ 、 $|A \cap B \cap C| = 3$ —— $|A \cup B \cup C|$ 等于？

（1 分）

A

$54$ （ $30 + 25 + 20 - 10 - 8 - 6 + 3$ ）

B

$57$

C

$51$

D

$60$

第 10 题 B4 未作答

判断题：错排数可用容斥推出—— $D(n) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ （"每人都不在自己位置" = 总数减去各种"有人在自己位置"的交集）。

（1 分）

A

正确

B

错误

第 11 题 B5 未作答

$1 \sim 100$ 中既不被 2 也不被 3 整除的数有多少个？

（1 分）

A

$33$ （ $100 - 50 - 33 + 16$ ）

B

$67$

C

$50$

D

$17$

第 12 题 B6 未作答

判断题：加法原理要求"分类互斥"；性质有重叠时不能直接相加——必须用容斥修正。容斥是加法原理的推广。

（1 分）

A

正确

B

错误

第 13 题 B7 未作答

$1 \sim 60$ 中被 2 或 3 或 5 整除的数有多少个？（被 2：30、被 3：20、被 5：12、被 6：10、被 10：6、被 15：4、被 30：2）

（1 分）

A

$44$ （ $30 + 20 + 12 - 10 - 6 - 4 + 2$ ）

B

$62$

C

$50$

D

$40$

叁

鸽巢原理

7 QUESTIONS · 2 POINTS EACH

第 14 题 C1 未作答

鸽巢原理（抽屉原理）的表述是？

（1 分）

A

$n+1$ 只鸽子放入 $n$ 个鸽巢，至少有一个巢有 $\ge 2$ 只鸽子

B

$n$ 只鸽子放入 $n$ 个巢，每巢恰 1 只

C

$n+1$ 只鸽子放入 $n+2$ 个巢，必有空巢

D

鸽子数与巢数无关

第 15 题 C2 未作答

加强版鸽巢原理： $kn + 1$ 只鸽子放入 $n$ 个巢，则？

（1 分）

A

至少有一个巢有 $\ge k+1$ 只鸽子

B

每巢恰 $k$ 只

C

至少有一巢空着

D

每巢至少 $k$ 只

第 16 题 C3 未作答

判断题：任意 $n+1$ 个整数中，必有两个数模 $n$ 同余（ $n$ 个余数类 = $n$ 个鸽巢）。

（1 分）

A

正确

B

错误

第 17 题 C4 未作答

判断题：鸽巢原理是存在性证明工具——它断言"必有"但不告诉你"是哪个"。

（1 分）

A

正确

B

错误

第 18 题 C5 未作答

至少多少个人，必有两个人生日在同一个月？

（1 分）

A

$13$ （12 个月 = 12 个巢，13 人必有同月）

B

$12$

C

$24$

D

$6$

第 19 题 C6 未作答

判断题：鸽巢原理只保证存在、不给出构造——但知道"必存在"常是进一步构造的起点。

（1 分）

A

正确

B

错误

第 20 题 C7 未作答

从 $1 \sim 100$ 中至少取多少个数，必有两个数之和为 101？

（1 分）

A

$51$ （50 对和为 101 的数对 + 1，取 51 个必有一对完整）

B

$50$

C

$100$

D

$26$

肆

卡特兰数

7 QUESTIONS · 2 POINTS EACH

第 21 题 D1 未作答

卡特兰数 $C_n$ 是？

（1 分）

A

一种著名组合数列： $C_0 = 1$ ， $C_n = \frac{1}{n+1}\binom{2n}{n}$

B

$C_n = 2^n$

C

$C_n = n!$

D

$C_n = \binom{n}{2}$

第 22 题 D2 未作答

卡特兰数第 $n$ 项的公式是？

（1 分）

A

$C_n = \dfrac{\binom{2n}{n}}{n+1}$

B

$C_n = \binom{2n}{n}$

C

$C_n = n!$

D

$C_n = 2^n$

第 23 题 D3 未作答

卡特兰数的递推公式是？

（1 分）

A

$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ （ $C_0 = 1$ ）

B

$C_n = C_{n-1} + C_{n-2}$

C

$C_n = n C_{n-1}$

D

$C_n = 2 C_{n-1}$

第 24 题 D4 未作答

判断题： $n$ 对括号的合法括号序列个数是卡特兰数 $C_n$ ——如 3 对括号有 5 种合法序列。

（1 分）

A

正确

B

错误

第 25 题 D5 未作答

判断题： $n$ 个元素的合法出栈序列个数是卡特兰数 $C_n$ ——如 1、2、3 的合法出栈序列有 5 种。

（1 分）

A

正确

B

错误

第 26 题 D6 未作答

判断题：卡特兰数还出现在—— $n$ 个节点的不同二叉树的个数、 $n \times n$ 网格不越过对角线的路径数、凸 $n+2$ 边形的三角剖分数。

（1 分）

A

正确

B

错误

第 27 题 D7 未作答

卡特兰数前几项是？

（1 分）

A

$1, 1, 2, 5, 14, 42$ （ $C_0$ 到 $C_5$ ）

B

$1, 2, 3, 4, 5, 6$

C

$1, 1, 2, 3, 5, 8$ （斐波那契）

D

$1, 2, 6, 24, 120$ （阶乘）

伍

错排

6 QUESTIONS · 2 POINTS EACH

第 28 题 E1 未作答

错排（Derangement）的定义是？

（1 分）

A

$n$ 个元素的排列中，没有元素在原来位置的排列（全错位排列）

B

排列顺序完全颠倒

C

任意排列

D

循环排列

第 29 题 E2 未作答

错排数的递推公式是？

（1 分）

A

$D(n) = (n-1)(D(n-1) + D(n-2))$ ， $D(1) = 0$ 、 $D(2) = 1$

B

$D(n) = n D(n-1)$

C

$D(n) = D(n-1) + D(n-2)$

D

$D(n) = n! - 1$

第 30 题 E3 未作答

错排数前几项是？

（1 分）

A

$D(1) = 0$ 、 $D(2) = 1$ 、 $D(3) = 2$ 、 $D(4) = 9$ 、 $D(5) = 44$

B

$1, 2, 6, 24, 120$

C

$0, 1, 3, 7, 15$

D

$1, 1, 2, 5, 14$

第 31 题 E4 未作答

判断题：错排的容斥推导： $D(n) = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots$ ——减去"至少一个在自己位置"的交集修正。

（1 分）

A

正确

B

错误

第 32 题 E5 未作答

$n$ 封信装入 $n$ 个信封全部装错的方式数是？

（1 分）

A

错排数 $D(n)$

B

$n!$

C

$(n-1)!$

D

$2^n$

第 33 题 E6 未作答

4 封信全部装错的方案数是？

（1 分）

A

$9$ （ $D(4)$ ）

B

$24$

C

$6$

D

$12$

陆

圆排列与二项式定理

6 QUESTIONS · 2 POINTS EACH

第 34 题 F1 未作答

$n$ 个不同元素围成一圈的圆排列数是？

（1 分）

A

$(n-1)!$ （旋转视为相同，固定一个位置再排）

B

$n!$

C

$n!/2$

D

$n(n-1)$

第 35 题 F2 未作答

判断题：圆排列数 = 线排列数 ÷ n——因为每个圆排列旋转 $n$ 次对应 $n$ 个线排列。

（1 分）

A

正确

B

错误

第 36 题 F3 未作答

二项式定理是？

（1 分）

A

$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$

B

$(a+b)^n = a^n + b^n$

C

$(a+b)^n = n(a+b)$

D

$(ab)^n = a^n + b^n$

第 37 题 F4 未作答

判断题： $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ ——二项式系数之和（ $(1+1)^n$ ）。

（1 分）

A

正确

B

错误

第 38 题 F5 未作答

$(a+b)^4$ 的展开系数是？

（1 分）

A

$1, 4, 6, 4, 1$

B

$1, 3, 3, 1$

C

$1, 5, 10, 10, 5, 1$

D

$4, 6, 4$

第 39 题 F6 未作答

判断题：圆排列与二项式定理都是排列组合的基本工具——圆排列处理"循环对称"、二项式定理给出展开系数。

（1 分）

A

正确

B

错误

柒

计数技巧综合

6 QUESTIONS · 2 POINTS EACH

第 40 题 G1 未作答

判断题：计数方法总表——加法原理（互斥相加）、乘法原理（分步相乘）、容斥（重叠修正）、鸽巢（存在性）、卡特兰/错排（特殊结构计数）。

（1 分）

A

正确

B

错误

第 41 题 G2 未作答

"至少满足一个性质"的计数问题首选方法是？

（1 分）

A

容斥原理

B

鸽巢原理

C

卡特兰数

D

错排

第 42 题 G3 未作答

判断题： $\binom{n}{k} = \binom{n}{n-k}$ （对称性）、 $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ （杨辉递推）——两大基本性质。

（1 分）

A

正确

B

错误

第 43 题 G4 未作答

判断题：古典概型概率 = 有利事件数 ÷ 总数——计数是概率的基础，容斥/错排常直接用于概率题。

（1 分）

A

正确

B

错误

第 44 题 G5 未作答

$1 \sim 100$ 中与 6 互质的数有多少个？（即不被 2 或 3 整除）

（1 分）

A

$33$

B

$67$

C

$50$

D

$17$

第 45 题 G6 未作答

判断题：计数题三大易错——重叠未修正（忘容斥）、对称未处理（圆排列忘除 n）、特殊结构未识别（卡特兰/错排场景当成普通排列）。

（1 分）

A

正确

B

错误

捌

易错综合

5 QUESTIONS · 2 POINTS EACH

第 46 题 H1 未作答

判断题：三集合容斥的符号是"+ 单 - 双 + 三"——把三重交集写成减号（或漏掉）都会算错。

（1 分）

A

正确

B

错误

第 47 题 H2 未作答

判断题：12 个人不一定有同月生日（12 人可各占一月）——鸽巢要求鸽子数 > 巢数，13 人才保证。

（1 分）

A

正确

B

错误

第 48 题 H3 未作答

判断题：卡特兰公式的分母是 $n+1$ （ $C_n = \binom{2n}{n}/(n+1)$ ）——记成 $n$ 或漏除都是常见错误。

（1 分）

A

正确

B

错误

第 49 题 H4 未作答

判断题：错排递推是 $D(n) = (n-1)(D(n-1) + D(n-2))$ ——忘乘 $(n-1)$ 是常见错误（那样就退化成斐波那契式了）。

（1 分）

A

正确

B

错误

第 50 题 H5 未作答

判断题：以下结论全部正确——"容斥加奇减偶；鸽巢 $n+1$ 进 $n$ 巢必有同巢；卡特兰 $C_4 = 14$ ；错排 $D(4) = 9$ ；圆排列 $(n-1)!$ "。

（1 分）

A

正确

B

错误

玖

容斥代码

6 QUESTIONS · 2 POINTS EACH

第 51 题 I1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int nA = 30, nB = 25, nAB = 10;    // |A|、|B|、|A∩B|
05    cout << nA + nB - nAB;             // |A∪B|
06    return 0;
07}

单选题：程序输出是？

（1 分）

A

45

B

55

C

65

D

40

第 52 题 I2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int A = 30, B = 25, C = 20;
05    int AB = 10, AC = 8, BC = 6, ABC = 3;
06    cout << A + B + C - AB - AC - BC + ABC;
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

54

B

57

C

51

D

48

第 53 题 I3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 100;
05    int c2 = n / 2, c3 = n / 3, c6 = n / 6;
06    cout << c2 + c3 - c6;       // 被 2 或 3 整除的个数
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

67

B

83

C

50

D

33

第 54 题 I4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 100;
05    int c2 = n / 2, c3 = n / 3, c6 = n / 6;
06    cout << n - c2 - c3 + c6;   // 不被 2 或 3 整除（与 6 互质）
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

33

B

67

C

50

D

17

第 55 题 I5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int A = 30, B = 25, AB = 10;
05    cout << ______;             // 两集合容斥
06    return 0;
07}

单选题：横线处应填入？（使输出为 45）

（1 分）

A

A + B - AB

B

A + B + AB

C

A * B - AB

D

A - B + AB

第 56 题 I6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 60;
05    int c2 = n / 2, c3 = n / 3, c5 = n / 5;
06    int c6 = n / 6, c10 = n / 10, c15 = n / 15, c30 = n / 30;
07    cout << c2 + c3 + c5 - c6 - c10 - c15 + c30;
08    return 0;
09}

单选题：程序输出是？（1~60 中被 2 或 3 或 5 整除的个数）

（1 分）

A

44

B

62

C

50

D

40

拾

鸽巢代码

6 QUESTIONS · 2 POINTS EACH

第 57 题 J1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int people = 13, months = 12;
05    cout << (people > months ? "SAME-MONTH" : "NOT-SURE");
06    return 0;
07}

单选题：程序输出是？（13 人 12 月——鸽巢保证同月）

（1 分）

A

SAME-MONTH

B

NOT-SURE

C

编译错误

D

13

第 58 题 J2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 5;                 // 5 个余数类（模 5）
05    int nums = 6;              // 6 个整数
06    cout << (nums > n ? "SAME-REMAINDER" : "NOT-SURE");
07    return 0;
08}

单选题：程序输出是？（6 个整数模 5，必有两个同余）

（1 分）

A

SAME-REMAINDER

B

NOT-SURE

C

编译错误

D

6

第 59 题 J3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int days = 366;            // 一年最多 366 天
05    int people = 367;          // 367 人
06    cout << (people > days ? "SAME-DAY" : "NOT-SURE");
07    return 0;
08}

单选题：程序输出是？（367 人必有 2 人同一天生日）

（1 分）

A

SAME-DAY

B

NOT-SURE

C

编译错误

D

367

第 60 题 J4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 1~100 分成 50 对和 101 的数对：(1,100),(2,99),...,(50,51)
05    // 取 51 个数，鸽巢保证必有一对两个都取到
06    int pairs = 50, taken = 51;
07    cout << (taken > pairs ? "SUM-101" : "NOT-SURE");
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

SUM-101

B

NOT-SURE

C

编译错误

D

51

第 61 题 J5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int pigeons = 10, holes = 9;
05    cout << (______ ? "DOUBLE" : "NOT-SURE");   // 鸽巢判定
06    return 0;
07}

单选题：横线处应填入？（使输出为 DOUBLE）

（1 分）

A

pigeons > holes

B

pigeons < holes

C

pigeons == holes

D

pigeons >= 2

第 62 题 J6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 加强版：kn+1 只鸽子 n 个巢 → 某巢 ≥ k+1 只
05    int k = 2, n = 5, pigeons = k * n + 1;
06    cout << pigeons / n + (pigeons % n ? 1 : 0);   // 至少某巢的下限
07    return 0;
08}

单选题：程序输出是？（11 只鸽子 5 个巢，某巢至少 ⌈11/5⌉ = 3 只）

（1 分）

A

3

B

2

C

11

D

5

拾壹

卡特兰代码

7 QUESTIONS · 2 POINTS EACH

第 63 题 K1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    long long c[4] = {0};
06    c[0] = 1;
07    for (int i = 1; i <= n; i++) {
08        c[i] = 0;
09        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
10    }
11    cout << c[3];       // C(3) = 5
12    return 0;
13}

单选题：程序输出是？

（1 分）

A

5

B

14

C

2

D

6

第 64 题 K2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    long long c[5] = {0};
06    c[0] = 1;
07    for (int i = 1; i <= n; i++)
08        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
09    cout << c[4];       // C(4) = 14
10    return 0;
11}

单选题：程序输出是？

（1 分）

A

14

B

5

C

42

D

9

第 65 题 K3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 3 对括号的合法序列数 = C(3) = 5
05    int n = 3;
06    long long c[4] = {0};
07    c[0] = 1;
08    for (int i = 1; i <= n; i++)
09        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
10    cout << c[n];
11    return 0;
12}

单选题：程序输出是？（3 对括号的合法括号序列个数）

（1 分）

A

5

B

6

C

4

D

3

第 66 题 K4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 3 个元素（1、2、3）的合法出栈序列数 = C(3) = 5
05    // 如 3 2 1、1 3 2、2 1 3、2 3 1、1 2 3；3 1 2 不合法
06    int n = 3;
07    long long c[4] = {0};
08    c[0] = 1;
09    for (int i = 1; i <= n; i++)
10        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
11    cout << c[n];
12    return 0;
13}

单选题：程序输出是？

（1 分）

A

5

B

6

C

4

D

7

第 67 题 K5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
06    return r;
07}
08int main() {
09    int n = 3;
10    cout << C(2 * n, n) / (n + 1);   // C(6,3)/4 = 20/4 = 5
11    return 0;
12}

单选题：程序输出是？

（1 分）

A

5

B

20

C

4

D

6

第 68 题 K6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 4;
05    long long c[5] = {0};
06    c[0] = ______;            // C(0) = 1
07    for (int i = 1; i <= n; i++)
08        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
09    cout << c[4];
10    return 0;
11}

单选题：横线处应填入？（使输出为 14）

（1 分）

A

1

B

0

C

2

D

4

第 69 题 K7 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 凸五边形（n+2 = 5 → n = 3）的三角剖分数 = C(3) = 5
05    int n = 3;
06    long long c[4] = {0};
07    c[0] = 1;
08    for (int i = 1; i <= n; i++)
09        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
10    cout << c[n];
11    return 0;
12}

单选题：程序输出是？（凸五边形的三角剖分方式数）

（1 分）

A

5

B

3

C

6

D

4

拾贰

错排代码

6 QUESTIONS · 2 POINTS EACH

第 70 题 L1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long d[6] = {0};
05    d[1] = 0; d[2] = 1;
06    for (int i = 3; i <= 5; i++) d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
07    cout << d[4];
08    return 0;
09}

单选题：程序输出是？（D(4)）

（1 分）

A

9

B

44

C

2

D

6

第 71 题 L2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long d[6] = {0};
05    d[1] = 0; d[2] = 1;
06    for (int i = 3; i <= 5; i++) d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
07    for (int i = 1; i <= 5; i++) cout << d[i] << " ";
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

0 1 2 9 44

B

1 2 6 24 120

C

0 1 1 2 3

D

1 1 2 5 14

第 72 题 L3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04long long C(int n, int k) {
05    long long r = 1;
06    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
07    return r;
08}
09int main() {
10    // D(4) = 4! - C(4,1)·3! + C(4,2)·2! - C(4,3)·1! + C(4,4)·0!
11    int n = 4;
12    long long d = 0;
13    for (int k = 0; k <= n; k++)
14        d += (k % 2 ? -1 : 1) * C(n, k) * fact(n - k);
15    cout << d;
16    return 0;
17}

单选题：程序输出是？

（1 分）

A

9

B

24

C

10

D

44

第 73 题 L4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 3 封信全部装错 = D(3) = 2
05    long long d[4] = {0};
06    d[1] = 0; d[2] = 1;
07    for (int i = 3; i <= 3; i++) d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
08    cout << d[3];
09    return 0;
10}

单选题：程序输出是？

（1 分）

A

2

B

6

C

1

D

3

第 74 题 L5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long d[6] = {0};
05    d[1] = 0; d[2] = 1;
06    for (int i = 3; i <= 5; i++) d[i] = ______;
07    cout << d[5];
08    return 0;
09}

单选题：横线处应填入？（使输出为 44）

（1 分）

A

(i - 1) * (d[i - 1] + d[i - 2])

B

d[i - 1] + d[i - 2]

C

i * d[i - 1]

D

(i - 1) * d[i - 1]

第 75 题 L6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 5 封信 5 个信封，恰有 2 封装对（其余 3 封全错）
05    long long d[4] = {0};
06    d[1] = 0; d[2] = 1;
07    d[3] = 2 * (d[2] + d[1]);   // D(3) = 2
08    long long C = 10;            // C(5,2) = 10
09    cout << C * d[3];
10    return 0;
11}

单选题：程序输出是？（恰 2 封装对的方案数 = C(5,2) × D(3)）

（1 分）

A

20

B

10

C

30

D

40

拾叁

圆排列与二项式代码

6 QUESTIONS · 2 POINTS EACH

第 76 题 M1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    int n = 5;
06    cout << fact(n - 1);    // 5 人围圆桌 = 4!
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

24

B

120

C

60

D

12

第 77 题 M2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    cout << fact(6);
06    return 0;
07}

单选题：程序输出是？

（1 分）

A

720

B

120

C

5040

D

600

第 78 题 M3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // (a+b)^4 的系数 = 杨辉第 5 行
05    int c[5][5] = {0};
06    for (int i = 0; i <= 4; i++) {
07        c[i][0] = c[i][i] = 1;
08        for (int j = 1; j < i; j++)
09            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
10    }
11    for (int j = 0; j <= 4; j++) cout << c[4][j] << " ";
12    return 0;
13}

单选题：程序输出是？

（1 分）

A

1 4 6 4 1

B

1 3 3 1

C

1 5 10 10 5 1

D

4 6 4

第 79 题 M4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int c[6][6] = {0};
05    for (int i = 0; i <= 5; i++) {
06        c[i][0] = c[i][i] = 1;
07        for (int j = 1; j < i; j++)
08            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
09    }
10    for (int j = 0; j <= 5; j++) cout << c[5][j] << " ";
11    return 0;
12}

单选题：程序输出是？

（1 分）

A

1 5 10 10 5 1

B

1 4 6 4 1

C

5 10 10 5

D

1 6 15 20 15 6 1

第 80 题 M5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // (1+1)^5 = 2^5 = 32 = 系数和
05    int c[6][6] = {0};
06    long long sum = 0;
07    for (int i = 0; i <= 5; i++) {
08        c[i][0] = c[i][i] = 1;
09        for (int j = 1; j < i; j++)
10            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
11    }
12    for (int j = 0; j <= 5; j++) sum += c[5][j];
13    cout << sum;
14    return 0;
15}

单选题：程序输出是？（ $(1+1)^5 = 32$ ）

（1 分）

A

32

B

16

C

64

D

31

第 81 题 M6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
06    return r;
07}
08int main() {
09    cout << C(10, 3);    // 10 人选 3 人
10    return 0;
11}

单选题：程序输出是？

（1 分）

A

120

B

720

C

30

D

90

拾肆

计数综合代码

6 QUESTIONS · 2 POINTS EACH

第 82 题 N1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
06    return r;
07}
08int main() {
09    cout << C(8, 2);
10    return 0;
11}

单选题：程序输出是？

（1 分）

A

28

B

56

C

16

D

20

第 83 题 N2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
06    return r;
07}
08int main() {
09    // 1~20 中不被 2 或 3 整除：20 - 10 - 6 + 3
10    cout << 20 - 20 / 2 - 20 / 3 + 20 / 6;
11    return 0;
12}

单选题：程序输出是？

（1 分）

A

7

B

13

C

10

D

4

第 84 题 N3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // "4 对括号的合法序列数" → 卡特兰 C(4) = 14
05    int n = 4;
06    long long c[5] = {0};
07    c[0] = 1;
08    for (int i = 1; i <= n; i++)
09        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
10    cout << c[n];
11    return 0;
12}

单选题：程序输出是？

（1 分）

A

14

B

5

C

42

D

8

第 85 题 N4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    // 3 封信随机装 3 个信封，全部装错的概率 = D(3)/3! = 2/6
06    int D3 = 2, total = 6;
07    cout << D3 << "/" << total;
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

2/6

B

1/6

C

2/3

D

1/3

第 86 题 N5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    // 4 人围圆桌、其中两人必须相邻：捆绑成 1 个 → 3 个"整体"圆排列 × 内部 2!
06    cout << fact(3 - 1) * 2;
07    return 0;
08}

单选题：程序输出是？（3 个整体圆排列 $(3-1)! = 2$ ，内部 $2! = 2$ ）

（1 分）

A

4

B

12

C

6

D

24

第 87 题 N6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * (n - i) / (i + 1);
06    return r;
07}
08int main() {
09    cout << C(20, 10);
10    return 0;
11}

单选题：程序输出是？（C(20,10) = 184756）

（1 分）

A

184756

B

92378

C

167960

D

184755

拾伍

完善程序

7 QUESTIONS · 2 POINTS EACH

第 88 题 O1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 100;
05    int c2 = n / 2, c3 = n / 3, c6 = n / 6;
06    cout << n - c2 - c3 + ______;   // 不被 2 或 3 整除
07    return 0;
08}

单选题：横线处应填入？（使输出为 33）

（1 分）

A

c6

B

c2

C

c3

D

0

第 89 题 O2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int people = 13, months = 12;
05    cout << (______ ? "SAME" : "NOT-SURE");
06    return 0;
07}

单选题：横线处应填入？（使输出为 SAME）

（1 分）

A

people > months

B

people == months

C

people < months

D

people >= 1

第 90 题 O3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    long long c[4] = {0};
06    c[0] = 1;
07    for (int i = 1; i <= n; i++)
08        for (int j = 0; j < i; j++) c[i] += ______;
09    cout << c[3];
10    return 0;
11}

单选题：横线处应填入？（使输出为 5）

（1 分）

A

c[j] * c[i - 1 - j]

B

c[j] + c[i - 1 - j]

C

c[i - 1]

D

c[j] * 2

第 91 题 O4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long d[6] = {0};
05    d[1] = 0;
06    d[2] = ______;        // D(2) = 1
07    for (int i = 3; i <= 5; i++) d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
08    cout << d[4];
09    return 0;
10}

单选题：横线处应填入？（使输出为 9）

（1 分）

A

1

B

0

C

2

D

6

第 92 题 O5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    int n = 6;
06    cout << fact(______);   // n 人圆排列 = (n-1)!
07    return 0;
08}

单选题：横线处应填入？（使输出为 120）

（1 分）

A

n - 1

B

n

C

n + 1

D

n - 2

第 93 题 O6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int c[5][5] = {0};
05    for (int i = 0; i <= 4; i++) {
06        c[i][0] = c[i][i] = 1;
07        for (int j = 1; j < i; j++)
08            c[i][j] = ______;     // 杨辉递推
09    }
10    cout << c[4][2];
11    return 0;
12}

单选题：横线处应填入？（使输出为 6）

（1 分）

A

c[i - 1][j - 1] + c[i - 1][j]

B

c[i - 1][j - 1] * 2

C

c[i][j - 1] + c[i - 1][j]

D

c[i - 1][j] + c[i][j]

第 94 题 O7 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long C(int n, int k) {
04    long long r = 1;
05    for (int i = 0; i < k; i++) r = r * ______ / (i + 1);
06    return r;
07}
08int main() {
09    cout << C(10, 3);
10    return 0;
11}

单选题：横线处应填入？（使输出为 120）

（1 分）

A

(n - i)

B

(n + i)

C

n

D

(k - i)

拾陆

代码易错

6 QUESTIONS · 2 POINTS EACH

第 95 题 P1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 60;
05    int c2 = n / 2, c3 = n / 3, c5 = n / 5;
06    int c6 = n / 6, c10 = n / 10, c15 = n / 15;
07    // 错误：漏了三重交集 +c30
08    cout << c2 + c3 + c5 - c6 - c10 - c15;
09    return 0;
10}

单选题：程序输出是？（漏 +c30 的错误结果；正确应为 44）

（1 分）

A

42

B

44

C

40

D

50

第 96 题 P2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int people = 12, months = 12;
05    cout << (people >= months ? "SAME" : "NOT-SURE");   // 错误：>= 而非 >
06    return 0;
07}

单选题：程序输出是？（12 人 12 月不保证同月——12 人可各占一月，判定应为 NOT-SURE）

（1 分）

A

SAME（错误结论——边界条件应为 >）

B

NOT-SURE

C

编译错误

D

12

第 97 题 P3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    long long c[4] = {0};
06    c[0] = 0;                    // 错误：C(0) 应为 1
07    for (int i = 1; i <= n; i++)
08        for (int j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
09    cout << c[3];
10    return 0;
11}

单选题：程序输出是？（C(0)=0 导致全部算出 0）

（1 分）

A

0

B

5

C

1

D

2

第 98 题 P4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long d[6] = {0};
05    d[1] = 1;                    // 错误：D(1) 应为 0
06    d[2] = 1;
07    for (int i = 3; i <= 5; i++) d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
08    cout << d[3];
09    return 0;
10}

单选题：程序输出是？（D(1)=1 的初值错误使 D(3) 变成 4，正确应为 2）

（1 分）

A

4

B

2

C

6

D

9

第 99 题 P5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03long long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
04int main() {
05    int n = 5;
06    cout << fact(n);      // 错误：忘了圆排列要除 n（应 (n-1)! = 24）
07    return 0;
08}

单选题：程序输出是？（把圆排列当线排列算的结果）

（1 分）

A

120

B

24

C

60

D

20

第 100 题 P6 未作答

判断题：以下结论全部正确——"容斥符号加奇减偶；鸽巢边界是鸽子 > 巢数（严格大于）；卡特兰 C(0) = 1 初值；错排 D(1) = 0、D(2) = 1；圆排列要除 n"。

（1 分）

A

正确

B

错误

重置作答

第 25 章 组合计数进阶 · 知识细节练习

判 分 报 告

容斥原理

容斥应用

鸽巢原理

卡特兰数

错排

圆排列与二项式定理

计数技巧综合

易错综合

容斥代码

鸽巢代码

卡特兰代码

错排代码

圆排列与二项式代码

计数综合代码

完善程序

代码易错

打印

导出 HTML 子卷

第 25 章组合计数进阶 · 知识细节练习

判分报告