集合

一、概念解析

集合的数学定义

集合是离散数学中的基础概念，用于描述具有某种共同属性的元素的整体，在信奥赛中常用于处理元素去重、存在性判断和逻辑关系运算。

集合的概念解析

1. 集合的数学定义

• 基本特性：

  • 无序性：集合中的元素没有顺序（如 ${1,2}$ 与 ${2,1}$ 是同一集合）；
  • 唯一性：集合中不存在重复元素（如 ${1,1,2}$ 等价于 ${1,2}$）；
  • 确定性：元素是否属于集合是明确的（如“所有偶数”是集合，“很大的数”不是集合）。

• 核心运算：

  • 交集（$(A \cap B)$）：由同时属于 $A$ 和 $B$ 的元素组成的集合；
  • 并集（$(A \cup B)$）：由属于 $A$ 或 $B$ 的元素组成的集合；
  • 差集（$(A - B)$）：由属于 $A$ 但不属于 $B$ 的元素组成的集合；
  • 补集（$(\complement_U A)$）：在全集 $(U)$ 中，不属于 $(A)$ 的元素组成的集合。

2. C++中的集合实现方式

信奥赛中常用以下数据结构模拟集合，各有适用场景：

实现方式	特点（优势/劣势）	适用场景
布尔数组	元素范围小（如 $0 \leq x \leq 10^5$），查询 $O(1)$，空间与范围正相关	元素为连续整数且范围已知（如标记1~n中的数）
std::set	自动去重，有序存储，插入/查询 $O(\log n)$，支持迭代	元素范围大，需有序遍历或频繁插入删除
std::unordered_set	哈希存储，无序，插入/查询平均 $O(1)$，哈希冲突时退化	只需去重和存在性判断，无需有序
比特集（bitset）	极端节省空间（1字节存8个元素），操作高效，大小编译时固定	元素范围固定且较小（如 $x \leq 10^6$）

二、实战案例

实战案例

案例1：用布尔数组实现集合基本运算

问题：已知集合 $A$ 和 $B$ 的元素为1~100的整数，求 $A \cap B$、$A \cup B$ 和 $A - B$。

c++

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 101; // 元素范围1~100

// 输出集合元素
void printSet(const vector<bool>& s) {
    cout << "{";
    bool first = true;
    for (int i = 1; i < MAX; ++i) {
        if (s[i]) {
            if (!first) cout << ",";
            cout << i;
            first = false;
        }
    }
    cout << "}" << endl;
}

int main() {
    vector<bool> A(MAX, false), B(MAX, false);
    
    // 初始化集合A: 2的倍数
    for (int i = 2; i < MAX; i += 2) A[i] = true;
    // 初始化集合B: 3的倍数
    for (int i = 3; i < MAX; i += 3) B[i] = true;
    
    // 计算交集 A ∩ B
    vector<bool> intersection(MAX, false);
    for (int i = 1; i < MAX; ++i) {
        if (A[i] && B[i]) intersection[i] = true;
    }
    
    // 计算并集 A ∪ B
    vector<bool> unionSet(MAX, false);
    for (int i = 1; i < MAX; ++i) {
        if (A[i] || B[i]) unionSet[i] = true;
    }
    
    // 计算差集 A - B
    vector<bool> difference(MAX, false);
    for (int i = 1; i < MAX; ++i) {
        if (A[i] && !B[i]) difference[i] = true;
    }
    
    cout << "A: "; printSet(A);
    cout << "B: "; printSet(B);
    cout << "A∩B: "; printSet(intersection);
    cout << "A∪B: "; printSet(unionSet);
    cout << "A-B: "; printSet(difference);
    return 0;
}

关键点：布尔数组通过索引直接映射元素，用 true/false 标记是否属于集合，运算通过逻辑判断实现，适合小范围元素。

案例2：用std::set处理动态集合

问题：动态添加元素到集合，去重后输出，并判断某个元素是否存在。

c++

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s; // 自动去重且有序
    int n;
    cin >> n;
    
    // 添加元素（重复元素会被自动忽略）
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        s.insert(x); // 插入，O(log n)
    }
    
    // 输出集合（自动按升序排列）
    cout << "去重后集合: ";
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl;
    
    // 判断元素是否存在
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (s.find(x) != s.end()) { // 查找，O(log n)
            cout << x << " 存在" << endl;
        } else {
            cout << x << " 不存在" << endl;
        }
    }
    return 0;
}

优势：set 自动处理去重和排序，适合元素范围不确定或需要有序遍历的场景，insert 和 find 操作效率稳定。

案例3：容斥原理（并集计数）

问题：计算1~n中能被2、3或5整除的数的个数（利用 $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$）。

c++

#include <iostream>
using namespace std;

// 计算1~n中能被k整除的数的个数
int countDivisible(int n, int k) {
    return n / k;
}

int main() {
    int n;
    cin >> n;
    int A = countDivisible(n, 2);   // 能被2整除的数
    int B = countDivisible(n, 3);   // 能被3整除的数
    int C = countDivisible(n, 5);   // 能被5整除的数
    
    int AB = countDivisible(n, 6);  // 2和3的最小公倍数是6，A∩B
    int AC = countDivisible(n, 10); // 2和5的最小公倍数是10，A∩C
    int BC = countDivisible(n, 15); // 3和5的最小公倍数是15，B∩C
    
    int ABC = countDivisible(n, 30); // 2,3,5的最小公倍数是30，A∩B∩C
    
    // 容斥公式计算并集个数
    int result = A + B + C - AB - AC - BC + ABC;
    cout << "1~" << n << "中能被2、3或5整除的数有" << result << "个" << endl;
    return 0;
}

原理：容斥原理是集合并集计数的核心工具，通过加减交集实现，避免重复计数（如同时被2和3整除的数在A和B中各算一次，需减去一次）。

三、信奥赛应用场景

信奥赛应用场景

1. 去重与统计：
   如“统计输入中不同数字的个数”（用set或unordered_set自动去重，返回size()）。

2. 存在性判定：
   如“判断某个数是否在之前的输入中出现过”（用find操作，O(1)或O(log n)效率）。

3. 范围筛选：
   如“找出两个数组中都出现的元素”（求交集，遍历较小集合检查是否在另一集合中）。

4. 容斥原理计数：
   如“计算1~n中不能被任何质数整除的数的个数”“统计满足多个条件的元素总数”。

5. 状态标记：
   如“标记已访问的节点”“记录已使用的数字”（布尔数组或bitset高效标记）。

四、避坑指南

避坑指南

1. 数据结构选择错误：

   • 陷阱：对元素范围大（如 $10^9$）的场景用布尔数组，导致内存溢出；对需要频繁查找的场景用set而非unordered_set，效率低下。
   • 解决：小范围（≤1e6）用布尔数组/bitset，大范围且需快速查找用unordered_set，需有序遍历用set。

2. 去重逻辑遗漏：

   • 陷阱：用vector手动实现集合时，添加元素前未检查是否已存在，导致重复（如if (find(v.begin(), v.end(), x) == v.end()) v.push_back(x)）。
   • 解决：优先用set自动去重；手动实现时，确保添加前检查存在性（注意vector的find是O(n)，效率低）。

3. 容斥原理符号错误：

   • 陷阱：计算多集合并集时，加减交集的符号错误（如三集合并集漏加+|A∩B∩C|）。
   • 解决：牢记容斥公式规律：奇数个集合的交集相加，偶数个集合的交集相减（从单个集合开始，依次交替）。

4. 空集处理不当：

   • 陷阱：对空集进行运算时逻辑错误（如求空集与任何集合的交集时返回非空，或遍历空集导致异常）。
   • 解决：运算前判断集合是否为空（如if (s.empty())），空集的交集为空，与非空集的并集为非空集。

5. unordered_set的哈希限制：

   • 陷阱：对自定义类型（如结构体）使用unordered_set，未提供哈希函数，导致编译错误。
   • 解决：自定义类型需重载operator()或提供哈希函数；或改用set（只需重载<运算符）。

重要

• 核心作用：集合是处理离散元素的基础工具，解决去重、存在性判断、范围筛选等问题，容斥原理是集合计数的核心思想。
• 实现选择：根据元素范围、是否需要有序、操作频率（插入/查询）选择数据结构（布尔数组/set/unordered_set），平衡空间与时间效率。
• 竞赛提示：普及组中集合问题多与去重、计数结合，需熟练掌握基本运算和容斥原理，尤其注意数据结构的合理选择和边界情况（如空集、重复元素）的处理，避免因效率或逻辑错误丢分。

加法原理

一、概念解析

加法原理

加法原理是组合数学中计数问题的基础原理，用于计算“不重叠”情况下的总方案数，是信奥赛中解决分类计数问题的核心工具。

概念解析

1. 基本定义

• 核心思想：若完成一件事有 $n$ 类不同的方法，第1类方法有 $m_1$ 种，第2类方法有 $m_2$ 种，……，第 $n$ 类方法有 $m_n$ 种，且各类方法互不重叠（即一种方法属于且仅属于一类），则完成这件事的总方法数为：

  $$N = m_1 + m_2 + \dots + m_n$$

• 关键条件：

  • 互斥性：各类方法之间没有交集（一种情况不能同时属于两类）；
  • 完整性：所有可能的方法都被包含在这些类别中。

2. 与乘法原理的区别

原理	适用场景	核心逻辑	示例（从A到B的路线数）
加法原理	分类完成，各类方法互斥	“或”关系（任选一类）	走陆路有3种，走水路有2种，总方法：3 + 2 = 5
乘法原理	分步完成，各步方法关联	“与”关系（各步都选）	先乘船有2种，再乘车有3种，总方法：2 × 3 = 6

二、实战案例

实战案例

案例1：基础分类计数

问题：一个商店出售铅笔、钢笔和圆珠笔。铅笔有3种颜色，钢笔有2种品牌，圆珠笔有4种款式。小明想买一支笔，共有多少种选择？

c++

#include <iostream>
using namespace std;

int main() {
    // 三类笔的选择数（互斥）
    int pencils = 3;   // 铅笔
    int pens = 2;      // 钢笔
    int ballpoints = 4; // 圆珠笔
    
    // 总选择数 = 各类选择数之和（加法原理）
    int total = pencils + pens + ballpoints;
    
    cout << "总选择数：" << total << endl; // 输出 3+2+4=9
    return 0;
}

关键点：买铅笔、钢笔、圆珠笔是互斥的（只能选一种），直接求和即可。

案例2：含限制条件的分类计数

问题：求1~100中能被2整除或能被3整除的数的个数（利用加法原理结合集合思想）。

c++

#include <iostream>
using namespace std;

// 计算1~n中能被k整除的数的个数
int countDivisible(int n, int k) {
    return n / k;
}

int main() {
    int n = 100;
    // 能被2整除的数（A类）
    int A = countDivisible(n, 2);
    // 能被3整除的数（B类）
    int B = countDivisible(n, 3);
    // 既能被2又能被3整除的数（A和B的交集，需减去重复计数）
    int AB = countDivisible(n, 6);
    
    // 加法原理修正：总个数 = A + B - AB（容斥原理的简单形式）
    int total = A + B - AB;
    
    cout << "1~100中能被2或3整除的数有：" << total << endl; // 输出 50 + 33 - 16 = 67
    return 0;
}

关键点：当两类方法有重叠（如数字6既能被2整除也能被3整除），需用容斥原理修正（减去重复部分），避免重复计数。

案例3：分步中的分类计数

问题：小明从家到学校有2条路，从学校到图书馆有3条路；此外，小明也可以从家直接到图书馆有2条路。求从家到图书馆的总路线数。

c++

#include <iostream>
using namespace std;

int main() {
    // 路线1：家 -> 学校 -> 图书馆（分步，用乘法原理）
    int route1 = 2 * 3; // 2条家到学校，3条学校到图书馆
    // 路线2：家 -> 图书馆（直接走，1类方法）
    int route2 = 2;
    
    // 总路线数 = 两类路线之和（加法原理）
    int total = route1 + route2;
    
    cout << "总路线数：" << total << endl; // 输出 6 + 2 = 8
    return 0;
}

原理：“间接路线”和“直接路线”是互斥的两类方法，分别计算后求和（加法原理），其中间接路线内部用乘法原理（分步）。

三、信奥赛应用场景

信奥赛应用场景

1. 路径计数问题：
   如“从起点到终点的不同路径数，其中路径分为两类：经过A点和不经过A点”，分别计算两类路径数后求和。

2. 组合数计算：
   如“从n个元素中选k个，其中某元素必须选或必须不选”，分两类计算：必须选（剩余n-1选k-1）和必须不选（剩余n-1选k），总和为 $C(n-1, k-1) + C(n-1, k)$。

3. 数字统计问题：
   如“计算1~n中不含数字3的数的个数”，按位数分类（1位数、2位数、……、最高位数），每类内部按位规则计数后求和。

4. 集合划分问题：
   如“将n个元素分成非空子集的方法数”，按第一个元素所在子集的大小分类，求和得到贝尔数。

5. 概率计算基础：
   如“计算某事件发生的概率”，先按互斥的情况分类，计算各类概率后求和。

四、避坑指南

避坑指南

1. 忽略方法重叠（未用容斥）：

   • 陷阱：直接将有重叠的两类方法数相加（如案例2中直接计算 $A + B$），导致重复计数。
   • 解决：若类别有交集，需用容斥原理修正（减去交集，若有多类则交替加减）。

2. 分类不完整：

   • 陷阱：遗漏部分可能的方法（如计算“小于10的质数”时，漏算2或5），导致结果偏小。
   • 解决：分类时确保“不重不漏”，可按固定规则（如按范围、特征、步骤）划分，必要时枚举验证。

3. 混淆加法与乘法原理：

   • 陷阱：将“分步”问题误用加法（如“先选上衣再选裤子”用加法），或将“分类”问题误用乘法（如“选上衣或裤子”用乘法）。
   • 解决：判断逻辑关系：“或”关系用加法（任选一类），“与”关系用乘法（各步都选）。

4. 数据范围溢出：

   • 陷阱：累加大量方法数时（如 $10^5$ 类，每类 $10^5$ 种），结果超过 int 范围（如 $1e10$ 超过 int 上限 $2e9$）。
   • 解决：用 long long 存储总和，避免中间结果溢出。

5. 边界条件处理错误：

   • 陷阱：分类时未考虑极端情况（如n=0或k=0时的组合数），导致逻辑漏洞。
   • 解决：单独处理边界情况（如0的阶乘为1，空集的计数为1），确保分类覆盖所有可能。

重要

• 核心价值：加法原理是分类计数的基础，通过将复杂问题分解为互斥的子问题，求和得到总方案数，是解决组合计数问题的“第一思路”。
• 应用要点：使用前需确认分类的“互斥性”和“完整性”，有重叠时结合容斥原理修正，与乘法原理结合可解决更复杂的分步+分类问题。
• 竞赛提示：普及组中加法原理常与数字统计、路径计数、组合数计算结合，需重点训练分类逻辑（如何划分不重叠的子问题），避免因重复计数或遗漏类别导致错误。

乘法原理

一、概念解析

乘法原理

乘法原理是组合数学中处理分步计数问题的核心原理，与加法原理共同构成计数理论的基础，在信奥赛中广泛应用于计算多步骤事件的总方案数。

概念解析

1. 基本定义

• 核心思想：若完成一件事需要经过 $n$ 个相互独立的步骤，第1步有 $m_1$ 种方法，第2步有 $m_2$ 种方法，……，第 $n$ 步有 $m_n$ 种方法，则完成这件事的总方法数为：

  $$N = m_1 \times m_2 \times \dots \times m_n$$

• 关键条件：

  • 分步性：事件需分解为多个有序步骤，缺一不可；
  • 独立性：每一步的方法数不受其他步骤影响（无论前一步选哪种方法，后一步的方法数不变）。

2. 与加法原理的对比

原理	核心逻辑	关键词	示例（从A到C的路线数）
加法原理	分类计数（任选一类）	“或”关系	直接到C有2条路，经B到C有3条路，总：2 + 3 = 5
乘法原理	分步计数（各步都选）	“与”关系	先到B有2条路，再从B到C有3条路，总：2 × 3 = 6

二、实战案例

实战案例

案例1：基础分步计数

问题：一个密码锁由3位数字组成（每位可填0~9），求总共有多少种可能的密码？

c++

#include <iostream>
using namespace std;

int main() {
    // 每位数字有10种选择（0~9），共3步
    int step1 = 10; // 第1位
    int step2 = 10; // 第2位
    int step3 = 10; // 第3位
    
    // 总密码数 = 各步方法数的乘积
    long long total = (long long)step1 * step2 * step3;
    
    cout << "总密码数：" << total << endl; // 输出 10×10×10=1000
    return 0;
}

关键点：每位数字的选择是独立步骤，用乘法原理直接相乘，注意用long long避免溢出（尤其多步骤时）。

案例2：含限制条件的分步计数

问题：用1、2、3、4、5组成无重复数字的3位数，共能组成多少个？

c++

#include <iostream>
using namespace std;

int main() {
    // 第1步：选百位数字（5种选择：1-5）
    int hundreds = 5;
    // 第2步：选十位数字（不能与百位重复，4种选择）
    int tens = 4;
    // 第3步：选个位数字（不能与前两位重复，3种选择）
    int units = 3;
    
    // 总个数 = 各步方法数的乘积
    int total = hundreds * tens * units;
    
    cout << "无重复数字的3位数个数：" << total << endl; // 输出 5×4×3=60
    return 0;
}

原理：虽然后一步的方法数依赖于前一步的选择（需去重），但每一步的方法数是确定的（前一步选完后剩余的数量），仍满足乘法原理的独立性条件（方法数固定）。

案例3：分步与分类结合

问题：小明从家到学校有2条路，从学校到图书馆有3条路；小红从家到图书馆有2条直接路线和3条经公园的路线。求小明和小红从家到图书馆的路线总数（两人路线相互独立）。

c++

#include <iostream>
using namespace std;

int main() {
    // 小明的路线：分步（家->学校->图书馆）
    int xiaoming = 2 * 3;
    // 小红的路线：分类（直接路线 + 经公园路线）
    int xiaohong = 2 + 3;
    
    // 总路线数：两人路线相互独立，用乘法原理
    int total = xiaoming * xiaohong;
    
    cout << "小明的路线数：" << xiaoming << endl;
    cout << "小红的路线数：" << xiaohong << endl;
    cout << "两人总路线组合数：" << total << endl; // 输出 6×5=30
    return 0;
}

关键点：先分别用乘法原理（小明）和加法原理（小红）计算各自的路线数，再用乘法原理计算两人的路线组合数（因相互独立）。

三、信奥赛应用场景

信奥赛应用场景

1. 排列组合问题：

   • 排列数 $P(n, k) = n \times (n-1) \times \dots \times (n-k+1)$（从n个元素中选k个排成一列）；
   • 可重复排列（如密码锁）：$n^k$（n种选择，共k步）。

2. 路径计数：
   如“网格中从(0,0)到(m,n)的最短路径数”，需向右走m步、向上走n步，共 $ \frac{(m+n)!}{m!n!} $ 种（本质是分步选择方向）。

3. 数字/字符串构造：
   如“计算不含重复数字的偶数的个数”，按个位（偶数）、首位（非0）、其他位的顺序分步计数。

4. 概率计算：
   如“计算连续两次掷骰子都出现6的概率”，分步计算每次概率后相乘（$ \frac{1}{6} \times \frac{1}{6} = \frac{1}{36} $）。

5. 算法复杂度分析：
   如嵌套循环的时间复杂度（外层循环n次，内层循环m次，总操作数为 $n \times m$）。

四、避坑指南

避坑指南

1. 步骤依赖性错误：

   • 陷阱：当后一步的方法数依赖于前一步的具体选择（而非固定数量）时，误用乘法原理（如“从2红3蓝球中依次取2个，求总取法”，若红球和蓝球无区别则为2步：5×4，但有区别时需分类）。
   • 解决：若步骤方法数不固定，需先分类（如分“先红后蓝”“先蓝后红”等），再对每类用乘法原理。

2. 溢出风险：

   • 陷阱：多步骤相乘时（如10步，每步10种方法，结果为 $10^{10}$），用int存储导致溢出（int最大约2×10⁹）。
   • 解决：始终用long long存储乘积结果，必要时对结果取模（如题目要求答案模1e9+7）。

3. 步骤顺序混淆：

   • 陷阱：分步顺序错误导致计数偏差（如计算“三位数中个位为偶数的个数”时，先算首位再算个位，而非相反）。
   • 解决：优先处理有约束的步骤（如个位必须为偶数），再处理无约束的步骤，减少重复计算。

4. 忽略“无选择”情况：

   • 陷阱：步骤中存在“必须选某一选项”的情况时，误将方法数算为0（如“密码第一位必须为1”，该步方法数为1而非0）。
   • 解决：明确每步的有效选择数（包括“唯一选择”的情况），即使方法数为1也要参与乘法（1不影响乘积结果）。

5. 与加法原理混淆：

   • 陷阱：将“分类”问题误用乘法（如“选语文书或数学书”用乘法），或将“分步”问题误用加法（如“先选语文书再选数学书”用加法）。
   • 解决：通过关键词判断：“先…再…”“依次…”用乘法；“或”“要么…要么…”用加法。

重要

• 核心价值：乘法原理是分步计数的基础工具，通过将复杂事件分解为独立步骤，相乘得到总方案数，是解决排列、路径、构造类问题的核心思想。
• 应用要点：使用时需确保事件可分解为有序、独立的步骤，每步方法数明确；与加法原理结合可处理“分类+分步”的复合问题（先分类，每类内部分步）。
• 竞赛提示：普及组中乘法原理常与数字构造、排列组合、路径计数结合，需重点训练分步逻辑（如何划分步骤、处理约束条件），并注意溢出防范和步骤顺序的合理性，避免因逻辑混淆导致错误。

排列

一、概念解析

排列

排列是组合数学中研究“有序选取”的核心概念，描述从给定元素中选取部分元素并按一定顺序排列的方式，是信奥赛中处理有序计数问题的基础工具。

概念解析

1. 基本定义

• 排列的数学定义：
  从 $n$ 个不同元素中，任取 $k$ 个（$1 \leq k \leq n$），按照一定顺序顺序排成一列，称为从 $n$ 个元素中取 $k$ 个的排列。所有可能的排列总数记为 $P(n, k)$ 或 $A(n, k)$。

• 计算公式：
  $P(n, k) = n \times (n-1) \times (n-2) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!}$
  其中 $n!$（读作“$n$ 的阶乘”）表示 $1 \times 2 \times \dots \times n$，规定 $0! = 1$。

• 全排列：当 $k = n$ 时，称为全排列，总数为 $P(n, n) = n!$。

2. 关键特性

• 有序性：排列与元素顺序相关（如 $ab$ 和 $ba$ 是不同的排列）；
• 不重复性：选取的元素互不重复（若允许放回选取）；
• 可变性：若允许元素重复选取（可放回），则排列数为 $n^k$（如密码锁的组合）。

二、实战案例

实战案例

案例1：计算排列数 $P(n, k)$

问题：从5名同学中选3人排成一队，计算有多少种不同的排法。

c++

#include <iostream>
using namespace std;

// 计算排列数 P(n, k) = n*(n-1)*...*(n-k+1)
long long permutation(int n, int k) {
    if (k < 0 || k > n) return 0; // 无效情况：k超出范围
    long long result = 1;
    for (int i = 0; i < k; ++i) {
        result *= (n - i); // 依次乘 n, n-1, ..., n-k+1
    }
    return result;
}

int main() {
    int n = 5, k = 3;
    cout << "从" << n << "人中选" << k << "人排成一队的排法数：" << permutation(n, k) << endl;
    // 输出：5×4×3 = 60
    return 0;
}

关键点：通过循环计算连乘积，避免直接计算阶乘（防止大数溢出），时间复杂度 $O(k)$。

案例2：生成全排列（递归法）

问题：输出3个元素 {1, 2, 3} 的所有全排列。

c++

#include <iostream>
#include <vector>
using namespace std;

// 递归生成全排列：arr为当前排列，used标记元素是否使用，nums为原始元素
void generatePermutations(vector<int>& arr, vector<bool>& used, vector<int>& nums) {
    // 递归终止：当前排列长度等于元素总数
    if (arr.size() == nums.size()) {
        for (int num : arr) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    
    // 尝试未使用的元素
    for (int i = 0; i < nums.size(); ++i) {
        if (!used[i]) {
            used[i] = true;          // 标记为已使用
            arr.push_back(nums[i]);  // 加入当前排列
            generatePermutations(arr, used, nums); // 递归
            arr.pop_back();          // 回溯：移除元素
            used[i] = false;         // 回溯：取消标记
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> arr;
    vector<bool> used(nums.size(), false);
    cout << "3个元素的全排列：" << endl;
    generatePermutations(arr, used, nums);
    return 0;
}

输出结果

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

原理：通过递归+回溯，每次选择一个未使用的元素加入排列，直到生成完整排列，再回溯尝试其他可能性。

案例3：含重复元素的排列

问题：计算 {1, 1, 2} 的不同全排列数（需去重）。

c++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 全局变量存储结果
vector<vector<int>> result;

// 递归生成含重复元素的全排列（去重）
void permuteUnique(vector<int>& nums, vector<int>& arr, vector<bool>& used) {
    if (arr.size() == nums.size()) {
        result.push_back(arr);
        return;
    }
    
    for (int i = 0; i < nums.size(); ++i) {
        // 跳过已使用的元素
        if (used[i]) continue;
        // 跳过重复元素（需先排序，确保相同元素相邻）
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        
        used[i] = true;
        arr.push_back(nums[i]);
        permuteUnique(nums, arr, used);
        arr.pop_back();
        used[i] = false;
    }
}

int main() {
    vector<int> nums = {1, 1, 2};
    sort(nums.begin(), nums.end()); // 排序是去重的前提
    vector<int> arr;
    vector<bool> used(nums.size(), false);
    
    permuteUnique(nums, arr, used);
    
    cout << "{1,1,2}的不同全排列数：" << result.size() << endl;
    cout << "全排列：" << endl;
    for (auto& p : result) {
        for (int num : p) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

输出结果

{1,1,2}的不同全排列数：3
全排列：
1 1 2 
1 2 1 
2 1 1

去重关键：先对元素排序，使相同元素相邻，递归时跳过“与前一个元素相同且前一个未使用”的元素，避免生成重复排列。

三、信奥赛应用场景

应用场景

1. 计数问题：

   • 如“计算用1~9组成无重复数字的3位偶数的个数”（先选个位，再选前两位）；
   • 排列数结合乘法原理：$P(n, k) = n \times P(n-1, k-1)$。

2. 生成排列：

   • 如“输出所有由1~n组成的不重复排列”（用于枚举验证或路径搜索）；
   • 全排列常作为回溯法的入门案例，扩展到子集生成、组合枚举等问题。

3. 字典序排列：

   • 如“求某个排列的下一个字典序排列”（利用STL的 next_permutation 函数）。

4. 密码与编码问题：

   • 如“计算由字母和数字组成的n位密码的总数”（可重复排列：$36^n$）。

5. 概率计算：

   • 如“计算从52张扑克牌中抽3张，恰好组成顺子的概率”（用排列数计算可能情况）。

四、避坑指南

避坑指南

1. 溢出风险：

   • 陷阱：计算 $n!$ 或 $P(n, k)$ 时，n稍大（如 $n \geq 20$）就会超过 long long 范围（$20! \approx 2.4e18$，接近 long long 上限）。
   • 解决：
     • 若题目要求取模（如模 $10^9+7$），边计算边取模；
     • 对大n（如 $n > 20$）且无取模要求，需用高精度算法（如用数组存储大整数）。

2. 重复元素处理错误：

   • 陷阱：含重复元素时直接套用全排列算法，生成大量重复结果（如 {1,1,2} 会生成6种排列，实际只有3种不同）。
   • 解决：先排序，再在递归中跳过重复元素（如案例3的去重逻辑）。

3. 递归栈溢出：

   • 陷阱：生成大n（如 $n \geq 1e4$）的全排列时，递归深度过深导致栈溢出。
   • 解决：
     • 大n场景下通常只需计算排列数，无需生成具体排列；
     • 若必须生成，改用非递归算法（如字典序法）。

4. STL函数的使用误区：

   • 陷阱：使用 next_permutation 时未先排序，导致只能生成从当前排列开始的后续排列，而非所有排列。
   • 解决：调用前必须对数组排序（如 sort(nums.begin(), nums.end())），确保从最小字典序开始生成。

5. 边界条件遗漏：

   • 陷阱：未处理 $k=0$（定义为1）、$k > n$（排列数为0）等特殊情况。
   • 解决：函数入口添加判断：if (k == 0) return 1; if (k > n) return 0;。

重要

• 核心价值：排列是研究“有序选取”的基础，其计数公式和生成方法是解决有序组合问题的核心工具，递归生成排列的思想可扩展到更复杂的回溯问题。
• 应用要点：计算排列数时优先用连乘法（避免阶乘溢出），生成排列时注意重复元素去重（排序+跳过重复），大n场景下聚焦计数而非枚举。
• 竞赛提示：普及组中排列问题多与计数、简单枚举结合，需熟练掌握排列数计算和基础回溯生成方法，重点防范溢出和重复元素处理错误，理解“有序性”是排列与组合的核心区别。

组合

一、概念解析

组合

组合是组合数学中研究“无序选取”的核心概念，描述从给定元素中选取部分元素而不考虑顺序的方式，是信奥赛中处理无顺序计数问题的基础工具。

概念解析

1. 基本定义

• 组合的数学定义：
  从 $n$ 个不同元素中，任取 $k$ 个（$0 \leq k \leq n$）组成一组（不考虑顺序），称为从 $n$ 个元素中取 $k$ 个的组合。所有可能的组合总数记为 $C(n, k)$ 或 $\binom{n}{k}$。

• 计算公式：
  $C(n, k) = \frac{P(n, k)}{k!} = \frac{n!}{k! \cdot (n-k)!}$
  其中 $P(n, k)$ 是排列数，$k!$ 用于消除因顺序不同而产生的重复计数。

• 性质：

  • $C(n, 0) = C(n, n) = 1$（选0个元素或全选的方式只有1种）；
  • 对称性：$C(n, k) = C(n, n-k)$（选k个等价于不选n-k个）；
  • 递推公式：$C(n, k) = C(n-1, k-1) + C(n-1, k)$（是否包含第n个元素分类）。

2. 与排列的核心区别

概念	核心差异	计算公式	示例（从{1,2,3}选2个）
排列	考虑顺序	$P(n,k) = \frac{n!}{(n-k)!}$	(1,2),(2,1),(1,3),(3,1),(2,3),(3,2) → 6种
组合	不考虑顺序	$C(n,k) = \frac{n!}{k!(n-k)!}$	{1,2},{1,3},{2,3} → 3种

二、实战案例

实战案例

案例1：计算组合数 $C(n, k)$

问题：从5名同学中选2人参加活动，有多少种不同的选法？

c++

#include <iostream>
using namespace std;

// 方法1：直接计算公式（适用于n和k较小的情况）
long long combination1(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    // 利用对称性减少计算量：C(n,k) = C(n,n-k)
    k = min(k, n - k);
    long long result = 1;
    for (int i = 1; i <= k; ++i) {
        // 先乘后除，避免中间结果溢出（利用整除性）
        result = result * (n - k + i) / i;
    }
    return result;
}

int main() {
    int n = 5, k = 2;
    cout << "从" << n << "人中选" << k << "人的组合数：" << combination1(n, k) << endl;
    // 输出：(5×4)/(2×1) = 10
    return 0;
}

关键点：

• 利用对称性 $k = \min(k, n-k)$ 减少乘法次数；
• 按 $\frac{(n-k+1) \times \dots \times n}{1 \times \dots \times k}$ 计算，先乘后除确保中间结果为整数（避免溢出）。

案例2：杨辉三角（递推法求组合数）

问题：用杨辉三角（帕斯卡三角）预处理 $C(n, k)$，用于多次查询。

c++

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 20; // 预处理到n=20

// 杨辉三角：c[i][j] = C(i,j)
vector<vector<long long>> precomputeCombinations() {
    vector<vector<long long>> c(MAX_N + 1, vector<long long>(MAX_N + 1, 0));
    for (int i = 0; i <= MAX_N; ++i) {
        c[i][0] = 1; // C(i,0) = 1
        c[i][i] = 1; // C(i,i) = 1
        for (int j = 1; j < i; ++j) {
            // 递推公式：C(i,j) = C(i-1,j-1) + C(i-1,j)
            c[i][j] = c[i-1][j-1] + c[i-1][j];
        }
    }
    return c;
}

int main() {
    auto c = precomputeCombinations();
    cout << "杨辉三角（部分）：" << endl;
    for (int i = 0; i <= 5; ++i) {
        for (int j = 0; j <= i; ++j) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
    // 输出C(5,2)
    cout << "C(5,2) = " << c[5][2] << endl; // 输出10
    return 0;
}

输出结果

杨辉三角（部分）：
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
C(5,2) = 10

优势：预处理后查询时间 $O(1)$，适合 $n \leq 1000$ 的多次查询场景。

案例3：生成所有组合（回溯法）

问题：输出从 {1,2,3,4} 中选2个元素的所有组合。

c++

#include <iostream>
#include <vector>
using namespace std;

// 回溯生成组合：start为起始索引（避免重复），current为当前组合
void generateCombinations(vector<int>& nums, int start, int k, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    // 从start开始遍历，确保组合内元素递增（去重）
    for (int i = start; i < nums.size(); ++i) {
        current.push_back(nums[i]);
        generateCombinations(nums, i + 1, k, current, result); // 下一个元素从i+1开始
        current.pop_back(); // 回溯
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int k = 2;
    vector<int> current;
    vector<vector<int>> result;
    
    generateCombinations(nums, 0, k, current, result);
    
    cout << "从{1,2,3,4}中选" << k << "个的组合：" << endl;
    for (auto& comb : result) {
        cout << "{";
        for (int i = 0; i < comb.size(); ++i) {
            if (i > 0) cout << ",";
            cout << comb[i];
        }
        cout << "}" << endl;
    }
    return 0;
}

输出结果

从{1,2,3,4}中选2个的组合：
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}

去重关键：通过 start 参数控制下一个元素的起始索引（必须大于当前元素索引），确保组合内元素递增，避免生成重复组合（如{1,2}和{2,1}视为同一组合）。

三、信奥赛应用场景

信奥赛应用场景

1. 组合计数问题：

   • 如“计算从n个物品中选k个的方式数”“求满足条件的子集个数”；
   • 结合加法原理：分类计算不同情况下的组合数再求和（如“从男生5人、女生3人中选2男1女的方式数：$C(5,2) \times C(3,1)$”）。

2. 概率计算：

   • 如“计算从52张牌中抽5张组成同花顺的概率”，分子为符合条件的组合数，分母为总组合数 $C(52,5)$。

3. 动态规划基础：

   • 如“爬楼梯问题：每次爬1或2阶，到n阶的方法数”对应组合数求和（$C(n-1,0) + C(n-2,1) + \dots$）。

4. 集合与子集问题：

   • 如“求n元素集合的子集总数”（$2^n = \sum_{k=0}^n C(n,k)$）。

5. 路径计数：

   • 如“网格中从(0,0)到(m,n)的最短路径数”为 $C(m+n, m)$（需走m步右和n步上，共选m步右）。

四、避坑指南

避坑指南

1. 溢出风险：

   • 陷阱：组合数增长极快（如 $C(20,10) = 184756$，$C(30,15) \approx 1.55e8$，$C(50,25) \approx 2.25e13$），易超出 int 范围。
   • 解决：
     • 用 long long 存储结果（可支持到 $C(30,15)$ 左右）；
     • 题目要求取模时（如模 $1e9+7$），预处理阶乘和逆元（扩展欧几里得或费马小定理）；
     • 大n场景（如 $n \leq 1e5$）需用组合数取模公式。

2. 递推法的空间浪费：

   • 陷阱：用杨辉三角预处理时，开二维数组存储所有 $C(n,k)$，当 $n=1e3$ 时需 $1e6$ 空间，n更大时内存不足。
   • 解决：用一维数组优化（滚动数组），仅保留上一行数据：
   c++

   vector<long long> c(n+1, 0);
   c[0] = 1;
   for (int i = 1; i <= n; ++i) {
       for (int j = i; j >= 1; --j) { // 逆序更新避免覆盖
           c[j] = c[j] + c[j-1];
       }
   }

3. 生成组合时的重复问题：

   • 陷阱：未控制起始索引，导致生成重复组合（如{1,2}和{2,1}）。
   • 解决：严格保证组合内元素递增（通过 start = i + 1 递归），确保每个组合仅生成一次。

4. 边界条件错误：

   • 陷阱：未处理 $k=0$、$k > n$ 等情况，导致计算错误（如 $C(5,6)$ 应返回0）。
   • 解决：函数入口添加判断：if (k < 0 || k > n) return 0; if (k == 0 || k == n) return 1;。

5. 除法取模错误：

   • 陷阱：计算组合数时直接对除法取模（如 $(a / b) \mod p \neq (a \mod p) / (b \mod p)$）。
   • 解决：用逆元转换除法为乘法：$(a / b) \mod p = (a \times b^{-1}) \mod p$，其中 $b^{-1}$ 是b在模p下的逆元。

重要

• 核心价值：组合是研究“无序选取”的基础，其计数公式和递推性质是解决子集、概率、路径等问题的核心工具，与排列共同构成组合数学的基石。
• 应用要点：计算组合数时优先用“先乘后除”的连乘公式（防溢出），多次查询时用杨辉三角预处理，生成组合时通过控制起始索引去重。
• 竞赛提示：普及组中组合问题多与计数、概率、子集生成结合，需熟练掌握组合数计算和基础回溯生成方法，重点防范溢出和边界条件错误，理解“无序性”是组合与排列的核心区别。

杨辉三角

一、概念解析

杨辉三角

杨辉三角（又称帕斯卡三角）是一种由数字排列成的三角形阵列，其核心特性是每行数字与组合数存在一一对应关系，是信奥赛中处理组合数计算、递推问题的重要工具。

杨辉三角

1. 基本定义与结构

• 结构特征：

  • 第0行只有1个元素：[1]；
  • 每行首尾元素均为1；
  • 其余元素等于其上方两元素之和（如第i行第j列元素 = 第i-1行第j-1列元素 + 第i-1行第j列元素）。

• 与组合数的关系：
  杨辉三角第i行（从0开始计数）的第j个元素（从0开始计数）恰好等于组合数 $( C(i, j) )$，即：
  $C(i, j) = \frac{i!}{j! \cdot (i-j)!}$

• 示例（前5行）：

console

第0行：1  
第1行：1 1  
第2行：1 2 1  
第3行：1 3 3 1  
第4行：1 4 6 4 1

其中第4行第2列元素为6，对应 $C(4, 2) = 6$。

2. 核心性质

• 对称性：第i行第j列元素与第i行第i-j列元素相等（对应组合数性质 $C(i, j) = C(i, i-j)$）；
• 递推性：$C(i, j) = C(i-1, j-1) + C(i-1, j)$（杨辉三角的构造基础）；
• 行和性质：第i行所有元素之和为 $2^i$（对应n元素集合的子集总数）。

二、实战案例

实战案例

案例1：构造杨辉三角（二维数组实现）

问题：输出前n行杨辉三角（n=5时如上述示例）。

c++

#include <iostream>
#include <vector>
using namespace std;

// 生成前n行杨辉三角
vector<vector<int>> generateYanghuiTriangle(int n) {
    vector<vector<int>> triangle;
    for (int i = 0; i < n; ++i) {
        vector<int> row(i + 1, 1); // 每行有i+1个元素，初始化为1
        // 填充中间元素（从第2行开始）
        for (int j = 1; j < i; ++j) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
        triangle.push_back(row);
    }
    return triangle;
}

// 打印杨辉三角
void printTriangle(const vector<vector<int>>& triangle) {
    for (const auto& row : triangle) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main() {
    int n = 5;
    cout << "前" << n << "行杨辉三角：" << endl;
    auto triangle = generateYanghuiTriangle(n);
    printTriangle(triangle);
    return 0;
}

关键点：利用递推性质，每行初始化首尾为1，中间元素通过上一行相邻元素之和计算，时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

案例2：优化空间的杨辉三角（一维数组实现）

问题：用滚动数组优化空间，仅用O(n)空间生成第n行杨辉三角。

c++

#include <iostream>
#include <vector>
using namespace std;

// 生成第n行杨辉三角（0-based）
vector<int> getNthRow(int n) {
    vector<int> row(n + 1, 0);
    row[0] = 1; // 第0行初始化为1
    
    for (int i = 1; i <= n; ++i) {
        // 从后往前更新，避免覆盖上一行数据
        for (int j = i; j >= 1; --j) {
            row[j] = row[j] + row[j - 1];
        }
    }
    return row;
}

int main() {
    int n = 4;
    cout << "第" << n << "行杨辉三角：" << endl;
    auto row = getNthRow(n);
    for (int num : row) {
        cout << num << " ";
    }
    // 输出：1 4 6 4 1
    return 0;
}

优化原理：利用一维数组逆序更新（从j=i到j=1），避免覆盖尚未使用的上一行数据，空间复杂度从 $O(n^2)$ 降至 $O(n)$。

案例3：杨辉三角的应用——计算组合数

问题：利用杨辉三角预处理组合数，快速查询 $C(n, k)$。

c++

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100; // 预处理到n=100
vector<vector<long long>> combTable;

// 预处理组合数表（杨辉三角）
void precomputeCombinations() {
    combTable.resize(MAX_N + 1, vector<long long>(MAX_N + 1, 0));
    for (int i = 0; i <= MAX_N; ++i) {
        combTable[i][0] = 1;
        combTable[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            combTable[i][j] = combTable[i-1][j-1] + combTable[i-1][j];
        }
    }
}

// 查询组合数 C(n, k)
long long getCombination(int n, int k) {
    if (k < 0 || k > n) return 0;
    return combTable[n][k];
}

int main() {
    precomputeCombinations();
    cout << "C(5, 2) = " << getCombination(5, 2) << endl; // 输出10
    cout << "C(10, 3) = " << getCombination(10, 3) << endl; // 输出120
    return 0;
}

优势：预处理后查询时间 $O(1)$，适合多次查询组合数的场景（如动态规划问题）。

三、信奥赛应用场景

信奥赛应用场景

1. 组合数快速查询：
   杨辉三角本质是组合数的递推表，预处理后可直接获取 $C(n, k)$，避免重复计算（如“从n个元素中选k个的方案数”）。

2. 动态规划基础模型：
   如“路径计数问题”：从网格左上角到右下角，每次只能右移或下移，到(i,j)的路径数为 $C(i+j, i)$，可通过杨辉三角递推计算。

3. 二项式定理展开：
   二项式 $(a + b)^n$ 的展开式系数对应杨辉三角第n行元素（如 $(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$，系数为第3行 [1,3,3,1]）。

4. 数论问题：
   如“求n以内所有数的约数个数和”，可利用杨辉三角的行和性质简化计算。

5. 递推关系训练：
   杨辉三角是理解递推思想的经典案例，可扩展到斐波那契数列、卡特兰数等其他递推问题。

四、避坑指南

避坑指南

1. 索引越界错误：

   • 陷阱：访问第i行第j列时，j超出范围（如第3行只有4个元素，却访问j=4）。
   • 解决：牢记第i行（0-based）有i+1个元素，j的范围是0~i，循环时严格控制j的边界。

2. 空间浪费：

   • 陷阱：对大n（如n=1e3）使用二维数组存储完整杨辉三角，占用 $1e6$ 空间。
   • 解决：若只需某一行或最新几行，用一维滚动数组（如案例2），空间复杂度降至O(n)。

3. 数据溢出：

   • 陷阱：组合数增长极快（第30行的中间元素已超过1e8），用int存储会溢出。
   • 解决：用long long存储元素；若n更大（如n=1e5），需结合取模运算（如模 $1e9+7$）。

4. 递推顺序错误：

   • 陷阱：一维数组实现时正序更新（j从1到i），导致覆盖上一行数据（如计算row[j]时，row[j-1]已被修改）。
   • 解决：必须逆序更新（j从i到1），确保使用的是上一行的原始值。

5. 0-based与1-based混淆：

   • 陷阱：混淆行和列的计数方式（如误将第1行当作第0行），导致查询组合数时出错。
   • 解决：统一使用0-based索引（行和列均从0开始），与组合数定义 $C(n,k)$ 保持一致。

重要

• 核心价值：杨辉三角是组合数的直观表现形式，其递推性质为组合数计算、动态规划等问题提供了高效解决方案，是理解递推思想的基础模型。
• 实现要点：二维数组适合生成完整三角，一维滚动数组适合空间敏感场景；利用递推公式时需注意边界和更新顺序，避免数据覆盖和溢出。
• 竞赛提示：普及组中杨辉三角常与组合数计算、路径计数结合，需熟练掌握其构造方法和优化技巧，重点防范索引越界和数据溢出，理解其与组合数的内在联系。