“1023”经典博文翻新——Quick Tutorial of Data Structures and Algorithms New Edition！本系列教程篇幅极长，建议使用PC网页端阅览。原版专为各类考试强化冲刺复习设计，新版已大幅扩充其他常用高级算法，适用于PAT、CCF-CSP等算法考试/竞赛。原理剖析大量使用叙述性的类C++伪代码或冗余编码，仅供快速理解。选读内容已用*或“【拓展】”标注。本系列博文中部分较宽的公式、代码块需使用横向滚动条完整查看，故不适合直接打印全文，如有必要请缩放文字大小至94%及以下。

对比原版《数据结构强化笔记》，新版除了可利用HyPress平台随时在线阅读外，还存在如下主要变化：

修正大量错词错字（Typo）
调整、简化了章节划分，部分“基础概念”“总结”性小节现已划至一级标题直属内容
大量追加红黑树、高级算法等全新章节与附录，其他各章亦有诸多扩充
全面优化了表述规范性（定义、定理、总结、Katex公式等）和代码风格，力求无漏洞、易读、易懂
调整重点内容标注方式，全面取消“下划线”高亮，调整了部分“荧光笔”（部分浏览器打印的PDF无法显示<mark>荧光笔高亮）“加粗”“斜体”高亮，提升阅览体验

Hyplus目录

1 数据结构基础

数据结构的基本概念：

数据（Data）：一切可被计算机识别并加工处理的对象，如整型、实型、布尔型、图像、字符、声音等
数据元素：由数据组成的具有一定意义的基本单位
- 数据项：组成数据元素的不可分割的最小单位
数据对象：性质相同的数据类型的集合，是数据的一个子集
数据结构（Data Structure）：由某一数据对象及该对象中所有元素之间的关系组成
数据类型：性质相同的值的集合以及定义在该值集上的运算的集合（本文用ElemType表示数据结构中元素的预定义类型）
- 原子类型：不可再分
- 结构类型：可再分为若干份数据类型
抽象数据类型（Abstract Data Type，ADT）：一个数学模型以及定义在其上的运算的集合，可用 $(D,S,P)$ 三元组表示，其中 $D$ 是数据对象， $S$ 是 $D$ 上的关系集， $P$ 是对 $D$ 的基本操作集。ADT定义模板如下所示

ADT DataType {
    数据对象: <数据对象的定义> // 伪代码实现
    数据关系: <数据关系的定义> // 伪代码实现
    基本操作: <基本操作的定义>
    /* 基本操作定义格式：
        1. 基本操作名（参数表：赋值参数只为操作提供输⼊值；指针、引⽤参数分别以<code>*</code>、<code>&</code>开头）
        2. 初始条件（初始条件描述）
        3. 操作结果（操作结果描述）  */
} ADT DataType

数据结构三要素：

逻辑结构：从逻辑上描述数据，与数据的存储⽆关；数据元素 + 关系
- 线性结构：数据元素之间存在⼀对⼀的关系(1:1)
  1. 线性表：具有相同数据类型的 $n\ (n>0)$ 个数据元素的有限序列
  2. 特殊线性表
    1. 栈：只能在⼀端进⾏插⼊删除，具有先进后出（FILO）的特性
    2. 队列：只能在⼀端进⾏插⼊、在另⼀端进⾏删除，具有先进先出（FIFO）的特性
    3. 字符串：元素为字符的线性表
  3. 扩展线性表结构
    1. 数组、矩阵：通常规定数组下标从 $\text{0}$ 开始，矩阵下标从 $\text{1}$ 开始
    2. ⼴义表：数据元素可以是原⼦，也可以是⼴义表
- 非线性结构
  1. 集合结构：数据元素除了同属于⼀个集合外，没有其他的关系
  2. 树形结构：数据元素之间存在⼀对多的关系(1:n)
    - 根据树的特点，分为⼀般树与 $m$ 叉树（其中二叉树最为常用）
  3. 图结构（⽹状结构）：数据元素之间存在多对多的关系(m:n)
    - 根据边是否为双向（即为弧），分为有向图与⽆向图
存储结构（物理结构）：逻辑结构在计算机内的映像
1. 顺序存储结构：将逻辑上相关的数据元素依次存储在地址连续的存储空间中，需要占⽤连续的存储空间
  - 优点：可以实现随机存取；每个元素占⽤最少的存储空间
  - 缺点：只能使⽤相邻的⼀⽚存储空间，可能产⽣较多的外部碎⽚
2. 链式存储结构：数据元素可以存储在连续或不连续的存储空间中，⽤指针相连，⽆需占⽤连续的存储空间
  - 优点：能充分利⽤所有存储单元，不会出现碎⽚现象
  - 缺点：指针占⽤额外的存储空间；且不⽀持随机存取，只能顺序存取
3. 索引存储结构：分别存放数据元素和元素间关系，建⽴附加的索引表来标识结点的地址
  - 优点：检索速度快（分块查找）
  - 缺点：附加的索引额外占⽤存储空间，增、删操作也需修改索引表，时间开销较⼤
4. 散列存储结构（哈希存储）：在数据元素的关键字与存储位置之间建⽴散列表，利⽤散列函数，计算记录的散列地址
  - 优点：增、删、查操作都很快
  - 缺点：散列函数不佳时容易产⽣冲突，⽽解决冲突会增加时间与空间开销
数据的运算
- 定义——逻辑结构：运算功能
- 实现——存储结构：运算的操作步骤
- 按功能分类（增删改查，CRUD）
  1. 查找运算：在数据结构中搜索满⾜⼀定条件的元素
  2. 插⼊运算：在数据结构中插⼊新元素
  3. 删除运算：在数据结构中删除指定元素
  4. 更新运算：在数据结构中将指定元素更新为新的元素
- 按效果分类
  1. 加⼯型运算：改变原数据结构
  2. 引⽤型运算：不改变原数据结构

【总结与归纳】逻辑结构与存储结构的概念

分清逻辑结构与存储结构

有序表——只表示逻辑结构，意味数据元素有序的线性表

顺序表、哈希表、单链表——既表示存储结构⼜表示逻辑结构，且逻辑结构独⽴于存储结构

单独说栈、队列、树、图等——都只表示逻辑结构，但循环队列包括了存储结构

对于两种不同的数据结构，逻辑结构或存储结构可能相同

2 算法与算法分析

算法（Algorithm）：对特定问题的求解步骤的一种描述，是指令的有限序列。算法可以用自然语言、流程图、程序设计语言或伪代码描述。当一个算法用程序设计语言描述时，便成为程序。

算法的五个特征（所有算法都满⾜）：

输入：算法有0个或多个输入
输出：算法至少产生一个输出
可行性：算法的每一条指令都足够基本，可以实现
确定性：算法的每一条指令都必须有确切的定义，没有二义性
有穷性：算法必须总能在执行有限步之后终止

算法与程序的最显著区别：算法必须是有穷的，但程序不⼀定满⾜有穷性

算法的设计要求（优质算法特性）：

正确性：算法执⾏结果应当满⾜预先规定的功能和性能要求
可读性：⼀个算法应当思路清晰，层次分明，易于阅读、理解，便于分析
健壮性：当输⼊⾮法数据时，应当能做适当处理，不⾄于产⽣莫名其妙的结果
通⽤性：算法应具有⼀般性，即算法的处理结果对于⼀般的数据集合都成⽴
⾼效性：执⾏效率⾼（时间⾼效），占⽤存储空间少（空间⾼效）

正确性的4个层次：

程序不含语法错误

程序对于⼏组输⼊数据能够得出满⾜规格说明要求的结果

程序对于典型、苛刻、带有刁难性的输⼊数据能够得出满⾜规格说明要求的结果【衡量程序合格的标准】

程序对于⼀切合法的输⼊数据都能够得出满⾜规格说明要求的结果

效率的度量：衡量算法效率的⽅法

事前分析估算——根据算法的规模和复杂度分析，与算法本身有关
事后计算⽅法——与算法运⾏时的硬件有关，不易发现算法本身的优劣，同⼀算法，编译器不同运⾏时间也不同

算法复杂度分析：

时间复杂度T(n)：程序运⾏从开始到结束所需的时间。算法中语句的执⾏次数称为语句频度，常作为计算时间复杂度的依据。可分为最好（T_{\text{best}}）、最坏（T_{\text{worst}}）、平均（T_{\text{avg}}）时间复杂度
- 渐近时间复杂度：若T(n)=a_m n^m + a_{m-1} n^{m-1} + \cdots +a_1n+a_0为m次多项式，则T(n)=O(n^m)
  - $O(\cdot)$ 表示上界， $\Omega(\cdot)$ 表示下界， $\Theta(\cdot)$ 表示紧界。为表述方便，本文一律使用大O表示法。
- 比较： $O(1) \lt O(\log n) \lt O(n) \lt O(n \log n) \lt O(n^2) \lt O(n^3) \lt O(2^n) \lt O(n!) \lt O(n^n)$
- 计算⽅法：
  1. 直接计算法：列出变量变化序列，找出跳出循环的条件（最后⼀项），反解，再取⼤O即可（多层循环直接相乘）
  2. 变形法：不等式放缩 + 两边取大O（应舍弃所有次量级项和系数）。【例】 $m+n ≤ 2\max(m,n) \Rightarrow O(m+n)=O(\max(m,n))$
空间复杂度S(n)：程序运⾏从开始到结束所需的存储量，⼀般按最坏情况来分析
- 组成：
  1. 固定部分：主要包括程序代码、常量、简单变量、定⻓成分的结构变量所占的空间。【例】const int N = 100;、ElemType data[MAXSIZE];
  2. 可变部分：该部分空间⼤⼩与算法在某次执⾏中处理的特定数据的⼤⼩和规模有关。【例】for、while循环
- 原地⼯作：所需空间为常量，即 $S(n)=O(1)$ ，并非指不占⽤空间！

【例】（408真题改）将⻓度分别为 $m,n$ 的升序链表合并成长度为 $m+n$ 的降序链表，计算最坏、最好时间复杂度（变形至最简）

【解】最坏和最好时间复杂度均为 $O(\max(m,n))$ ！

最坏情况即两条链表均各遍历了⼀遍，交替头插⾄新链表， $m+n≤2\max(m,n)$ ，两边取大O即有 $O(m+n)=O(2\max(m,n))=O(\max(m,n))$

最好情况即全程只遍历其中⼀条链表，然⽽另⼀条最终仍需顺次头插⾄新链表，故复杂度仍为 $O(m+n)=O(\max(m,n))$ 与最坏一样！

A 常用算法时间复杂度分析*

由数据范围反推算法时间复杂度。

对于时间限制为 $[1\text{s},2\text{s}]$ 的题目，C++代码中的操作次数应控制在 $[10^7,10^8]$ 为最佳。

数据范围	时间复杂度	算法
$n\leq30$	指数级	dfs+剪枝、状态压缩dp
$n\leq100$	$O(n^3)$	floyd、dp、高斯消元
$n\leq1000$	$O(n^2),O(n^2\log n)$	dp、二分、朴素dijkstra、朴素prim、Bellman-Ford
$n\leq10^4$	$O(n\sqrt n)$	块状链表、分块
$n\leq10^5$	$O(n\log n)$	sort、线段树、树状数组、set/map、heap、dijkstra+heap、spfa
$n\leq10^6$	① $O(n)$ ② 常数比较小的 $O(n\log n)$	① 单调队列、hash、双指针、bfs、并查集、kmp、AC自动机 ② sort、树状数组、heap、dijkstra+heap、spfa
$n\leq10^7$	$O(n)$	双指针、kmp、AC自动机、线性筛素数
$n\leq10^9$	$O(\sqrt n)$	判断质数
$n≤10^{18}$	$O(\log n)$	欧几里得算法、快速幂、数位dp

B C语言强化补充

源自“第0章 C语⾔强化补充笔记”，运算符优先级表新增了部分C++内容（范围解析）。

B.1 数据类型的⻓度

以下几类常用数据类型的长度随操作系统而变：

操作系统\数据类型	int	long	long long	指针
16位	2B	4B	-	2B
32位	4B	4B	8B	4B
64位	4B	8B	8B	8B

以下几类数据类型在任意操作系统均为固定长度：

数据类型	char	short	float	double
固定长度	1B	2B	4B	8B

结构体补齐：结构体变量的总大小为结构体变量中最大基本数据类型成员所占字节数的整数倍

B.2 运算符优先级

下表中数字越⼩，优先级越⾼（即“越先算”）：

优先级	运算符	结合方向
0	`::`（C++范围解析）	自左向右
1	`i++`（后缀自增） `i--`（后缀自减） `()`（圆括号/函数调用运算符） `[]`（数组下标） `.`（成员） `->`（指向成员）	`++` `--`：自右向左其他：自左向右
2	`++i`（前缀自增） `--`（前缀自减） `+`（正号） `-`（负号） `!`（逻辑非） `~`（按位取反） `(type)`（强制类型转换） `*`（指针） `&`（取地址/C++引用） `sizeof`（按字节确定大小）	自右向左
3	`*`（乘） `/` `%`	自左向右
4	`+`（加） `-`（减）	自左向右
5	`<<`（按位左移） `>>`（按位右移）	自左向右
6	`<` `<=` `>` `>=`	自左向右
7	`==` `!=`	自左向右
8	`&`（按位与）	自左向右
9	`^`（按位异或）	自左向右
10	`\|`（按位或）	自左向右
11	`&&`（逻辑与）	自左向右
12	`\|\|`（逻辑或）	自左向右
13	`? :`（三目条件运算符）	自右向左
14	`=` `+=` `-=` `*=` `/=` `%=` `&=` `^=` `\|=` `<<=` `>>=`	自右向左
15	`,`（逗号运算符）	自左向右

B.3 数据的输⼊输出

格式化输⼊（scanf）：格式字符串为%[*][宽度][类型长度]类型

类型（Type）：常用的格式类型如下表所示

数据类型格式	说明	进制数与特殊表示格式	说明
`%d`	整型（int）	`%o`	八进制
`%ld`	长整型（long int）	`%#o`	带前导的八进制
`%f`	单精度浮点型（float）	`%x`	十六进制
`%lf`	双精度浮点型（double）	`%#x`	带前导的十六进制
`%c`	字符（char）	`%s`	字符串

*：表示该输入项读入后不赋予相应变量，即跳过该输入值
- 【例】scanf("%d %*d %d", &a, &b);：输入1 2 3，使得a赋1，2被跳过，b赋3
宽度：用十进制整数指定输入的宽度（字符数）
- 【例】scanf("%4d%4d", &a, &b);：输入12345678，把1234赋给a、5678赋给b
类型长度：格式符有l（对应%ld、%lf）和h（对应%hd短整型数据）
- 注：scanf无法控制精度

格式化输出（printf）：格式字符串为%[标志][宽度][.精度][类型长度]类型，用*表示未指定

类型（Type）：常用的格式类型如下表所示

基本数据类型格式	说明	进制数与特殊表示格式	说明
`%u`	无符号整数（unsigned）	`%o`	八进制
`%d`	整型（int）	`%x` `%X`	十六进制
`%ld`	长整型（long int）	`%e`	以指数形式表示浮点数
`%f`	单精度浮点型（float）	`%p`	指针的值（地址）
`%lf`	双精度浮点型（double）	`%s`	字符串
`%c`	字符（char）

标志（Flags）：常用的标志格式如下表所示

标志	中文名	说明
`-`	减号	在给定的字段宽度内左对齐，右边填空格（无减号的默认情况为右对齐，左边填空格）
`+`	加号	强制显示符号（正号或负号）
	空格	输出为正时加上空格，为负时加上负号
`#`	井号	类型为`o`、`x`、`X`时，增加前缀`0`、`0x`、`0X`（同scanf）
`0`	数字零	使用前导零填充字段宽度，若出现了减号或指定了精度则忽略该标记

宽度：控制显示字段的宽度（包括小数点、正负号）
精度：指定输出精度（保留n位小数）
类型长度：同scanf的两种字符

转义字符：在字符串中会被自动转换为相应的特殊字符，常用的如下表所示

转义字符	说明	转义字符	说明
`\n` `\r`	回车换行	`\\`	反斜杠符（`\`）
`\t`	水平制表符	`\'`	单引号符（`'`）
`\v`	垂直制表符	`\"`	双引号符（`"`）
`\b`	退格	`\ddd`	1~3位八进制数（`ddd`）所代表的字符
`\f`	走纸换页	`\xhh`	1~2位十六进制数（`hh`）所代表的字符
`\a`	鸣铃

B.4 文件操作

文件指针：FILE *fp;

文件的打开与关闭
- fopen("文件名", "操作方式")：打开数据文件。打开失败返回NULL，否则返回指向该文件的指针。操作方式及增强符见下表
- fclose(fp)：关闭数据文件。正常关闭返回O，否则返回1

操作方式	名称	说明
`r`	读（read）	文件必须已存在，只能读出已有文件
`w`	写（write）	文件已存在，则删除原文件再重建一个新文件从头写数据文件不存在，则以指定文件名建立该文件从头写数据
`a`	追加（append）	文件必须已存在，只能在已有文件未追加数据

增强符	名称	说明
`t`	文本文件（text）	`rt`、`wt`、`at`，可省略不写
`b`	二进制文件（binary）	`rb`、`wb`、`ab`
`+`	读和写	`r+`、`wb+`、…

读写字符/字符串
- fputc('字符', fp)：将1个字符写进文件
- fgetc(fp)：从文件中输出当前所指的1个字符，直接返回它
- fputs("字符串", fp)：将字符串写进文件
- fgets("字符串", n, fp)：从文件中输出当前所指的n - 1个字符+字符串结束标记'\0'，赋值给字符数组
读取连续的数据块（按二进制）
- fread(数据地址, 每次读写的字节数size, 读写次数count, fp)
- fwrite(数据地址, 每次读写的字节数size, 读写次数count, fp)
格式化读写数据
- fprintf(fp, "格式说明", [输出列表])：将输出列表按格式说明输出至文件
- fscanf(fp, "格式说明", [输入列表])：从文件中按格式说明输入至输入列表
文件位置相关函数
- feof(fp)：测试文件位置指针（文件当前读写位置）是否在文件末尾，是则返回1，否则返回0
- rewind(fp)：将文件位置指针拨回开头，无返回值
- fseek(fp, 位移量, 起始点)：将文件位置指针从指定的起始点按指定位移量（长整型，数值后需加L或l）移动。相关常量如下表所示

起始点常量	值	说明
`SEEK_SET`	0	文件开头
`SEEK_CUR`	1	当前位置
`SEEK_END`	2	文档末尾

获取⽂件⻓度 ftell(fp)：返回当前位置相对⽂件头的位移量，返回-1L表示出错。如下例所示

/* 求文件a.txt的长度 */
FILE *fp = fopen("a.txt", "r");
fseek(fp, 0L, 2);
int fileLength = ftell(fp);

读取打开文件的内容 read(待读取文件, 保存读取内容的缓冲区, 读取文件的长度len)：返回实际读取的字节数

B.A 位运算*

常用的位运算技巧（例题）：

$n$ 的二进制表示中第 $k$ 位数字：n >> k & 1 （先把第 $k$ 位数字移到最后一位，再看个位是几，即和1做按位与运算）
lowbit(x) = x & -x：返回 $x$ 的最后一位1

/* 返回x的最后一位1 */
int lowbit(int x) {
    return x & -x;  // -x = ~x + 1
}

/* 输出整数x的二进制表示（31位）*/
void printBinary(int x) {
    for (int i = 0; i < 31; i++) {
        printf("%d", x >> i & 1);
    }
}

/* 统计x的二进制表示中有几位1 */
int countOnes(int x) {
    int cnt = 0;
    while (x) {
        x -= lowbit(x);
        cnt++;
    }
    return cnt;
}

B.B 进制转换*

/* 将p进制数x转换成10进制数，直接返回结果 */
int convertPTo10(int x, int p) {
    int res = 0, prod = 1;
    while (x) {
        res += (x % 10) * prod;
        x /= 10;
        prod *= p;
    }
    return res;
}

将10进制数 $d$ 转换成 $p$ 进制数：

/* 将10进制数d转换成p进制数，用vector存储结果 */
void convert10ToP(int d, int p, vector<int> &res) {
    while (d) {
        res.push_back(d % p);   // "除基取余"
        d /= p;
    }
}

C 数论与组合数学*

质数、约数、欧拉函数、快速幂、扩展欧几里得算法、高斯消元、组合数

更多数学相关优质内容：

高等数学（数二强化冲刺笔记）

线性代数（数二强化冲刺笔记）

概率论与数理统计

C.1 质数*

定义：在大于1的整数中，只包含1和本身这两个约数的数称为质数（素数）

试除法判定质数：

时间复杂度： $O(\sqrt n)$

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++) {  // 枚举到sqrt(x)
        if (x % i == 0) return false;
    }
    return true;
}

试除法分解质因数：

时间复杂度： $O(\sqrt n)$

vector<pair<int, int>> divide(int x) {
    vector<pair<int, int>> primes;  // 存储质因数及其个数
    for (int i = 2; i <= x / i; i++) {  // 枚举到sqrt(x)
        if (x % i == 0) {
            int cnt = 0;    // cnt记录质因子i的个数
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            primes.push_back({i, cnt});
        }
    }
    if (x > 1) {
        primes.push_back({x, 1});   // 原理：x中只包含1个大于sqrt(x)的质因子
    }
    return primes;
}

求素数表：

埃氏筛法求素数表：
- 时间复杂度： $O(n\log\log n)$

int primes[N], len; // 存储所有素数

/* 埃氏筛法求[2, n]上所有素数 */
void getPrimes(int n) {
    bool st[N] = {0};   // st[i]标记数i是否被筛掉
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {   // 仅遍历未被筛去的数，且只筛它的倍数
            primes[len++] = i;
            for (int j = i + i; j <= n; j += i) {   // 筛去i的倍数，朴素法遍历全部倍数
                st[j] = true;
            }
        }
    }
}

线性筛法求素数表：
- 核心思想：每个合数只会被其最小质因子筛掉。对于 $i$ 和素数 $P_j$ ，若 $i \bmod P_j=0$ ，且 $P_j$ 是 $i$ 的最小质因子，即一定是 $P_j \cdot i$ 的最小质因子。
- 时间复杂度： $O(n)$

int primes[N], len; // 存储所有素数

/* 线性筛法求[2, n]上所有素数 */
void getPrimes(int n) {
    bool st[N] = {0};   // st[i]标记数i是否被筛掉
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[len++] = i;
        }
        for (int j = 0; primes[j] <= n / i; j++) {  // primes[j] * i <= n
            st[primes[j] * i] = true;       // 每个合数只会被其最小质因子筛掉
            if (i % primes[j] == 0) break;  // 保证primes[j]一定是primes[j] * i的最小质因子
        }
    }
}

C.2 约数*

试除法求所有约数：

时间复杂度：取决于排序函数，试除的消耗为 $O(\sqrt n)$

/* 求所有约数（去重且递增排序） */
vector<int> getDivisors(int x) {
    vector<int> res;
    for (int i = 1; i <= x / i; i++) {  // 枚举到sqrt(x)
        if (x % i == 0) {   // 若i为x的约数，则x/i也是x的约数
            res.push_back(i);
            if (i != x / i) {
                res.push_back(x / i);   // 不重复存储约数sqrt(x)
            }
        }
    }
    sort(res.begin(), res.end());
    return res;
}

约数个数、约束之和：设 $N = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ ，其中 $p_i$ 为试除法求得的约数（个数为 $\alpha_i$ ），则

约数个数：

 $\begin{aligned} \prod^k\limits_{i=1}(\alpha_i+1)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1) \end{aligned}$

约数之和：

 $\begin{aligned} \prod^k\limits_{i=1}\left(\sum^{\alpha_i}\limits_{j=0}p_i^j)=(p_1^0+p_1^1+\cdots+p_1^{\alpha_1}\right)\cdots(p_k^0+p_k^1+\cdots+p_k^{\alpha_k}) \end{aligned}$

typedef long long LL;

const int MOD = 1e9 + 7;        // 防止结果过大而溢出

int x;
vector<pair<int, int> > primes; // 由试除法分解质因数函数divide()返回的数组，存储约数p_k及其个数a_k

/* 求约数个数 */
LL countDivisors() {
    LL cnt = 1;
    for (auto prime : primes) {
        cnt = cnt * (prime.second + 1) % MOD;
    }
    return cnt;
}

/* 求约数之和 */
LL sumDivisors() {
    LL sum = 1;
    for (auto prime: primes) {
        int p = prime.first, a = prime.second;  // 约数p与指数a
        LL t = 1;   // 记录p^0+...+p^a
        while (a--) {
            t = (t * p + 1) % MOD;      // 秦九韶算法
        }
        sum = sum * t % MOD;
    }
    return sum;
}

欧几里得算法求最大公约数：

整除的性质：若 $d \mid a,\ d \mid b$ ，则 $d \mid ax+by$

欧几里得算法（辗转相除法）公式：

 $\begin{aligned} \gcd(a,b)=\gcd(b,a \bmod b) \end{aligned}$

时间复杂度： $O(\log n)$

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;   // gcd(a, 0) = a
}

求最小公倍数：由欧几里得算法可得最小公倍数公式

 $\begin{aligned} \text{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)} \end{aligned}$

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

C.3 欧拉函数*

定义： $(1,N)$ 内与 $N$ 互质的数的个数称为欧拉函数，记为 $\phi(N)$ 。常规定 $\phi(1)=1$ 。

求法：若 $N=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$ ，则

 $\begin{aligned} \phi(N)=N\prod^m\limits_{i=1}\left (1-\dfrac1{p_i}\right ) \end{aligned}$

特别地，对于质数 $p$ ，有

 $\begin{aligned} \phi(p)=p-1 \end{aligned}$

C.4 快速幂*

求 $a^k \bmod p$ ，时间复杂度： $O(\log k)$

思想：

 $\begin{aligned} a^k\bmod p &=\prod\limits^{\log k}_{i=0}a^{2^i}\bmod p\\ a^{2^{i+1}}\bmod p &=(a^{2^i}\bmod p)^2\bmod p \end{aligned}$

核心：求 $k$ 的二进制表示，即

 $\begin{aligned} a^k\bmod p=\prod\limits_{i\in\{i\mid k[i]=1\}} a^{2^i}\bmod p \end{aligned}$

应用：求模为质数的逆元

逆元的定义： $ax\equiv 1\pmod m$ ， $a,m$ 互质，则称 $x$ 为 $a$ 模 $m$ 的逆元，记为 $a^{-1}$ 。

求法：当模为质数 $p$ 时，由费马小定理（见C.3）得

 $\begin{aligned} a^{\phi(p)}\equiv1\pmod p &\Rightarrow a^{p-1}\equiv 1\pmod p\\ &\Rightarrow a\cdot a^{p-2}\equiv1\pmod p \end{aligned}$

故可得逆元的公式（可用快速幂计算）：

 $\begin{aligned} a^{-1}=a^{p-2} \end{aligned}$

typedef long long LL;

/* a^k mod p */
LL qpow(int a, int k, int p) {
    LL res = 1, t = a;  // t记录a^2^i，其中i>=0，表示逻辑上当前迭代至k的第i位
    while (k) {
        if (k & 1) {
            res = res * t % p;  // 当k末位(k[i])为1时，结果乘上a^2^i mod p
        }
        t = t * t % p;  // 更新操作 t <- a^2^(i+1) mod p = (a^2^i mod p)^2 mod p
        k >>= 1;        // k去掉当前末位，使得逻辑上i++
    }
    return res;
}

C.5 扩展欧几里得算法*

裴蜀定理：对于任意正整数 $a, b$ ，存在非零整数 $x,y$ ，使得 $ax+by=\gcd(a,b)$ 。

求通解：设特解 $x_0,y_0$ 满足 $ax_0+b_0y=d$ ①，其中 $d=\gcd(a,b)$ 。原方程可化为 $a(x-\dfrac bd)+b(y+\dfrac ad)=d$ ②。由①②可得通解为

 $\begin{aligned} \left\{\begin{aligned} x=x_0-\frac bdk\\ y=y_0+\frac adk \end{aligned}\right. ,\ k\in \mathbb{Z^+} \end{aligned}$

应用：求解线性同余方程。对于方程 $ax\equiv b\pmod m$ ， $\exist y\in\mathbb{Z^+},\ ax=my+b\ \xRightarrow{y'=-y} ax+my'=b$ ，该方程有解的充要条件为 $\gcd(a,m)\mid b$ ，此时可用扩展欧几里得算法 $\text{exgcd}(a, b, x, y')$ 求得一组特解，进而求得原方程的解。特别地，求 $a$ 模 $m$ 的逆元即为 $b=1$ 的情况。

中国剩余定理：对于两两互质的 $k$ 个数 $m_1,m_2,\cdots,m_k$ ，线性同余方程组

 $\left\{\begin{matrix} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \vdots \\ x\equiv a_k\pmod{m_k} \end{matrix}\right.$

的通解为

 $\begin{aligned} x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+\cdots+a_kM_kM_k^{-1} \end{aligned}$

其中 $M=m_1m_2\cdots m_k$ ， $M_i=\dfrac{M}{m_i}\ (i=1,2,\cdots,k)$ ， $M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的逆元，可通过解 $M_ix\equiv1\pmod{m_i}$ 求得。

/* 求一组x, y特解，满足a*x + b*y = gcd(a, b)。函数返回最大公约数 */
int exgcd(int a, int b, int &x, int &y) {   // x, y用引用型
    if (!b) {   // gcd(a, 0) = a，此时a*x + 0*y = a的通解为(1, 任何数)
        x = 1;  // 这里传回特解(1, 0)
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);  // 将x、y翻转(便于对比条件)，使得b*y + (a mod b)*x = gcd(b, a mod b) = gcd(a, b)
    y -= (a / b) * x;   // a mod b = a - [a/b]*b，代入上式化简得a*x + b*(y - [a/b]*x) = d，对比条件可知y的变化量！
    return d;
}

C.6 高斯消元*

化增广矩阵为最简行阶梯形矩阵，解 $n$ 元线性方程组，时间复杂度： $O(n^3)$

const double eps = 1e-7;

int n;
double a[N][N]; // n*(n+1)的增广矩阵 a[0 ... n-1][0 ... n]

/* 0：有唯一解（此时将增广矩阵化为最简行阶梯形矩阵），1：有无穷多组解，2：无解 */
int gauss() {
    int c, r;   // 枚举的列、行（同时也记录实际方程个数）
    for (c = 0, r = 0; c < n; c++) {    // 枚举每一列c，最终化为行阶梯形矩阵
        int t = r;
        for (int i = r; i < n; i++) {   // 寻找绝对值最大的行，记录于t
            if (fabs(a[i][c]) > fabs(a[t][c])) {
                t = i;
            }
        }

        if (fabs(a[t][c]) < eps) continue;  // 若为0则无需消元，跳至下一列

        for (int i = c; i <= n; i++) {
            swap(a[t][i], a[r][i]); // 将绝对值最大的行t换到最顶端的当前行r
        }
        for (int i = n; i >= c; i--) {
            a[r][i] /= a[r][c]; // 将当前行r同除以该行首a[r][c]，使得行r首非零元变成1
        }
        for (int i = r + 1; i < n; i++) {// 用当前行r将行r首非零元该列下方所有元素消成0
            if (fabs(a[i][c]) > eps) {  // 若为0则无需再遍历操作该行，节省时间
                for (int j = n; j >= c; j--) {  // 行i同减行r各列同列元a[r][j]乘以行i首非零元a[i][c]（为了消之为0）
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }

        r++;    // 完成本列c消元操作后才跳至下一行
    }

    if (r < n) {    // 若化简后的方程个数小于n（最后n-r行系数阵部分全为0，即0行），则有无穷多组解或无解
        for (int i = r; i < n; i++) {   // 若某行左边为0而右边非0，则直接判无解
            if (fabs(a[i][n]) > eps) {
                return 2;   // 无解
            }
        }
        return 1;   // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i--) {  // 有唯一解则化为最简行阶梯形矩阵，列n所存的即为解
        for (int j = i + 1; j < n; j++) {   // 同化行阶梯形操作，用各行首非零元将其列上上全部元素消为0
            a[i][n] -= a[i][j] * a[j][n];
        }
    }
    return 0;   // 有唯一解
}

C.7 组合数*

组合数 $\text{C}_n^m$ （或 $\text{C}(n,m)$ 、 ${n \choose m}$ ）的定义式（从 $n$ 中取 $m$ 个）如下

 $\begin{aligned} \text{C}_n^m &=\dfrac{n\times(n-1)\times\cdots\times(n-m+1)}{1\times2\times\cdots\times m}\\ &=\dfrac{n!}{(n-m)!m!}\ (m\le n) \end{aligned}$

互补性：

 $\begin{aligned} \text{C}_n^m=\text{C}_n^{n-m} \end{aligned}$

递推式：

 $\begin{aligned} \text{C}_n^m=\text{C}_{n-1}^m+\text{C}_{n-1}^{m-1} \end{aligned}$

递推法求组合数：

适用于处理 $10^5$ 量级的数据量、 $1\leqm\leqn\leq2000$ 的情况
时间复杂度： $O(n^2)$

const int MOD = 1e9 + 7;    // 防止结果过大溢出

int c[N][N];    // c[i][j]即为C(i, j)，表示从i个不同元素中取j个的方案数

/* 计算C(0, 0) ~ C(N-1, N-1) */
void calc() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) {
                c[i][j] = 1;    // 规定“取0个/不取”算作只有1种方案
            } else {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
            }
        }
    }
}

通过逆处理逆元的方式求组合数： $\text{C}_n^m=n!\cdot((n-m)!)^{-1}\cdot (m!)^{-1}$ ，其中 $((n-m)!)^{-1},(m!)^{-1}$ 分别为 $(n-m)!,m!$ 模 $p$ 的逆元， $p$ 为质数。由费马小定理得逆元公式 $a^{-1}=a^{p-2}$ ，运用快速幂即可快速求解。

适用于处理 $10^4$ 量级的数据量、 $1\leqm\leqn\leq10^5$ 的情况
时间复杂度： $O(n\log n)$

typedef long long LL;       // 预处理时临时防爆int

const int MOD = 1e9 + 7;    // 防止结果过大溢出

int fact[N];    // fact[i]存储i的阶乘再取模
int infact[N];  // infact[i]存储fact[i]的模为质数的逆元再取模

/* qpow(a, k, p)：快速幂（a^k mod p）模板，用于求模为质数的逆元 */
// 详见前述

/* 预处理阶乘的余数fact[]和阶乘逆元的余数infact[] */
void init() {
    fact[0] = infact[0] = 1;    // 0! = 1，1的任何逆元为1
    for (int i = 1; i < N; i++) {   // 递推求解
        fact[i] = (LL) fact[i - 1] * i % MOD;
        infact[i] = (LL) infact[i - 1] * qpow(i, MOD - 2, MOD) % MOD;
    }
}

/* C(a, b)的值 */
int C(int a, int b) {
    return fact[a] * infact[a - b] * infact[b] % MOD;
}

Lucas定理：若 $p$ 为质数，则对于任意整数 $1\leqp\leqm\leqn$ ，有

 $\begin{aligned} \text{C}_n^m \equiv \text{C}_{n \bmod p}^{m \bmod p}\text{C}_{n/p}^{m/p}\pmod p \end{aligned}$

适用于较低数据量、 $1≤m≤n≤10^{18},1≤p≤10^5$ 的情况
时间复杂度： $O(\log_p n\cdot p\log p)$

typedef long long LL;

/* qpow(a, k, p)：快速幂（a^k mod p）模板，用于求模为质数的逆元 */
// 详见前述

/* 求int型数的组合数C(a, b) */
int C(int a, int b, int p) {
    if (a < b) return 0;

    LL x = 1, y = 1;    // 由最初的定义式，x为分子，y为分母
    for (int i = a, j = 1; j <= b; i--, j++) {
        x = x * i % p;  // x = a! / (a-b)!
        y = y * j % p;  // y = b!
    }

    return x * qpow(y, p - 2, p) % p;   // 结果即为x * (y的逆元) mod p
}

/* 通过Lucas定理求long long型数的组合数lucas(a, b) */
int lucas(LL a, LL b, int p) {
    if (a < p && b < p) return C(a, b, p);  // a, b都小于p时用逆元法即可
    return (LL) C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

分解质因数法求组合数：不取模，求出组合数的真实值——

筛法求出范围内的所有质数
通过组合数定义式 $\text{C}_n^m=\dfrac{n!}{(n-m)!m!}$ 求出每个质因子的次数： $n!$ 中 $p$ 的次数为 $\dfrac np + \dfrac n{p^2} + \dfrac n{p^3} + \cdots$
用高精度乘法将所有质因子相乘

int n;
int primes[N], len; // 存储所有质数
int sum[N];         // 存储每个质数的次数
bool st[N];         // 存储每个数是否已被筛掉

/* getPrimes(n)：线性筛法求素数，存至primes[] */
// 详见“线性筛法求素数”

/* 求n!中质因子p的次数：n / p + n / p^2 + n / p^3 + ... */
int get(int n, int p) {
    int res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

/* mul(A, b)：高精度乘低精度模板 */
// 详见对应篇章

/* 预处理范围n以内所有质因子，存储每个质因子的个数 */
void init(int a, int b) {   // a、b为所求组合数C(a, b)的上下标
    getPrimes(a);
    for (int i = 0; i < len; i++) { // 求每个质因子的次数
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p); // C(a, b) = a! / ((a - b)! * b!)
    }
}

/* 用高精度乘法将所有质因子相乘，存于数组 */
void calc() {
    vector<int> res;
    res.push_back(1);   // 初值为1
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < sum[i]; j++) {  // 乘sum[i]次primes[i]
            res = mul(res, primes[i]);
        }
    }
}

卡特兰数（Catalan Number）： $n$ 个不同元素进栈，出栈元素不同排列的个数（更多栈相关性质见3.1.2）

 $\begin{aligned} \text{Catalan}(n)=\dfrac{\text{C}_{2n}^n}{n+1} \end{aligned}$

int catalan(int n) {
    return C(2 * n, n) / (n + 1)
}

数据结构强化笔记（1）：绪论与前置知识

1 数据结构基础

2 算法与算法分析

A 常用算法时间复杂度分析*

B C语言强化补充

B.1 数据类型的⻓度

B.2 运算符优先级

B.3 数据的输⼊输出

B.4 文件操作

B.A 位运算*

B.B 进制转换*

C 数论与组合数学*

C.1 质数*

C.2 约数*

C.3 欧拉函数*

C.4 快速幂*

C.5 扩展欧几里得算法*

C.6 高斯消元*

C.7 组合数*

发表评论取消回复

1 数据结构基础

2 算法与算法分析

A 常用算法时间复杂度分析*

B C语言强化补充

B.1 数据类型的⻓度

B.2 运算符优先级

B.3 数据的输⼊输出

B.4 文件操作

B.A 位运算*

B.B 进制转换*

C 数论与组合数学*

C.1 质数*

C.2 约数*

C.3 欧拉函数*

C.4 快速幂*

C.5 扩展欧几里得算法*

C.6 高斯消元*

C.7 组合数*

发表评论 取消回复

发表评论取消回复