信息学竞赛

欧拉函数记为 $\varphi$，$\varphi(n)$ 代表 $1 \sim n$ 内与 $n$ 互质的数的个数。 欧拉函数有两种求法，下面分别说： 直接求 我们设 $p$ 为 $n$ 的质因子集合（非可重集），那么 $\varphi(n)=n \times \prod\limits_{x \in p} \left( \dfrac{x-1}{x} \right)$，原理： 我们设 $s$ 为目前与 $n$ 互质的数的集合，初始为 ${ 1,2,\dots,n }$。 每次遍历到一个 $p$ 中的数 $x$，就会筛掉这个集合中 $\dfrac{1}{x}$ 的数，即那些是 $x$ 的倍数的数，由于 $p$ 是去重后的质因子集合，所以当前集合的大小总是 $x$ 的倍数。 所以这个做法就能证明了，每乘一次 $\dfrac{x-1}{x}$，都相当于筛掉当前集合内 $\dfrac{1}{x}$ 的数，集合大小动态维护。 模板代码：（代码中的 $p$ 数组是提前筛出来的质数集合，$ind$ 为其大小） LL phi(LL n){ if(n == 0) return 0; LL ret = n; rep(i, 1, ind){ if(n % p[i] == 0) ret = ret * 1 - ret / p[i], n /= p[i]; while(n % p[i] == 0) n /= p[i]; } if(n > 1) ret = ret * 1 - ret / n; return ret; } 通过线性筛预处理 线性筛模板： void shai(LL n){ f[0] = f[1] = true; rep(i, 2, n){ if(!f[i]) p[++ind] = i; for(LL j = 1;i * p[j] <= n;j++){ f[i * p[j]] = true; if(i % p[j] == 0) break; } } } 线性筛有一个性质，就是在第二重循环里，每次都会筛掉数 $i \times p_j$，而 $p_j$ 正是这个数（$i \times p_j$）的最小质因子。 ...

我们现在要解决一个问题，就如标题所说，我们要判断一个DAG的拓扑序是否唯一。 以下说两种做法。 做法1（推荐） 在拓扑排序时，我们只要每时每刻都判断一下，此时的队列大小是否大于 $1$ 即可。 因为，如果队列大小大于 $1$，则选择任何一个元素都可以加入到拓扑序的最后下标，所以拓扑序不唯一。 做法2 （以下是我考试时想出来的做法，思维难度较高，但整个构思过程中都没有思维跳跃） 1 首先，我们建出这个DAG，然后我们考虑，其实一个DAG唯一，有且仅当对于所有点对 $(u,v)$（$1 \leq u,v \leq n$），都满足以下两点之一： 点 $u$ 可以到达点 $v$。 点 $v$ 可以到达点 $u$。 此处证明一下。 其实，如果存在一个不满足上述条件的点对 $(u,v)$，那么整张图可能会张这样：（下面标记的 $(u,v)$ 只是其中一个） 在这种情况里，我们直接把红色集合和蓝色集合里的拓扑序“交换”，变成： 于是乎，就得到了另一个合法的拓扑序，证毕。 关于如果满足条件，则拓扑序唯一，此处不多赘述，自行脑补。 2 上述条件还可以继续变化，变成： 对于所有点对 $(u,v)$（$1 \leq u,v \leq n$，且 $v$ 的拓扑序比 $u$ 的要大），都满足点 $u$ 可以到达点 $v$。 3 我们考虑定义函数 $f(x)$ 代表拓扑序为 $x$ 的节点，是否能到达所有拓扑序为 $y$（$x<y$）的点。 4 我们考虑求 $f(x)$，我们可以枚举拓扑序为 $x$ 的节点 $u$ 的所有出点 $v$（设其拓扑序为 $y$，且排除 $y \leq x$ 的所有点）。 ...

说到平衡树，很多人的第一印象就是： 难学（知识点真多） 难懂（特别是“旋转”和证明） 难调（我的某个教练刚学平衡树的时候调了七个小时） 下面我们就来从0开始讲平衡树。 （注：网上大多数人说到“平衡树”默认指的是“Splay”而不是其他算法） 定义 其实平衡树（Balance Tree，简称BT）不算一种算法，而是一种统称。 平衡树顾名思义就是非常平衡的树。 比如说这棵树就非常不平衡： 而这棵树就比较平衡： 如果说的更形式化，平衡就意味着，对于每个点，其所有子树的大小差都不超过 $1$。 具体而言，对于每个点 $x$，如果我们把其所有儿子 $to$ 的子树大小都列出来，那么这个数组内最大值和最小值差不超过 $1$。 而且，大多数平衡树都是二叉树，这一点是为了方便操作和设计算法。 种类 听完上面的定义，你就知道了，平衡树就是一类树状数据结构的统称。 下面就来列举一下这类数据结构都有哪些，以及这些数据结构的简介。 二叉搜索树（Binary Search Tree，简称BST） 大多数平衡树的前置算法，这也就意味着，大多数的平衡树都是基于BST并进行优化、扩展后得到的算法。 而BST也是线段树（Segment Tree，部分情况下会简称为ST）进行扩展后的算法。 具体而言，权值线段树和BST都可以维护有序集合，但有时候只能用BST解决。 BST其实就是把权值“当做”节点编号（讲的时候一般就这么讲，但写的时候不能这么写，是把权值存入该节点的结构体内）。 然后对于每个点，它都有最多 $2$ 个儿子，左儿子权值 $<$ 当前点权值 $<$ 右儿子权值。 这样就可以方便查找。 优点：代码好写，容易讲明白 缺点：解决题型少，需要写定期重构（又被称作“替罪羊树思想”），复杂度高 Treap（名字不是一个单词，而是两个单词Tree和Heap的结合） 这个算法给每个节点都添加了一个“优先级”，并让“优先级”满足小/大根堆的性质。 并且，这里还通过“旋转”操作（最头疼的地方来了）让树尽量平衡，这样会让树高稳定在 $O(\log n)$ 级别。 （不过注意，在最坏情况下，复杂度会达到 $O(n)$，所以 $O(\log n)$ 只是期望） 这样，复杂度就降下来了。 优点：复杂度低，比较容易理解，解决题型多，且容易被识别出 缺点：比较难写，细节较多，复杂度难证明 Splay（本意为“张开”但这里不是这个意思） 这个算法对上面的“旋转”操作又做了一遍扩展，让其能够解决子串翻转问题。 而且，由于它也会让整棵树尽量平衡，所以树高还是会稳定在 $O(\log n)$ 级别。 ...

参考 引用头文件（常用） #include <stdlib.h> //生成随机数、设定随机数种子 #include <ctime> //生成随机数种子（1） #include <time.h> //生成随机数种子（2） #include <unistd.h> //等待（sleep(...)或usleep(...)），该头文件现在不常用 随机种子 srand(time(0) ^ clock()); 注：随机种子为time(0) ^ clock()，这个随机种子可以再毫秒级别内生成（大概率）不同的随机种子。 取 $[l,r]$ 内的随机数 #define random(l, r) (rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l)) 注：rand函数只能生成 $[1,32767]$ 内的随机数（见宏RAND_MAX），大概只能生成位数 $\leq 5$ 的随机数；测试程序： LL ma = 0; for(LL i = 1;i <= 200;i++){ srand(time(0) ^ clock()); LL t = rand(); cout << t <<endl; ma = max(ma, t); usleep(10000); } cout << ma <<endl; 所以此处引用一个新方法：mt19937（2022/12/24：现在开始使用mt19937_64了，它可以生成 $[1,2^{64})$ 内的随机数，大一倍）。 其实它的语法和rand的语法差不多 （才怪），是这样的： 引用头文件（常用） #include <random> //生成随机数、设定随机数种子 #include <ctime> //生成随机数种子（1） #include <time.h> //生成随机数种子（2） #include <unistd.h> //等待（sleep(...)或usleep(...)），该头文件现在不常用 随机种子 mt19937 _rand(time(0) ^ clock()); 注：这个随机种子也可以再毫秒级别内生成（大概率）不同的随机种子 取 $[l,r]$ 内的随机数 （就差一个字符_而已） #define random(l, r) (_rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l)) 据测试，这个函数可以生成在unsigned int范围内的随机数（即可以生成 $[1,2^{32})$ 内的随机数），测试程序： ...

第一次看到树链剖分（简称树剖）可能觉得它非常的深奥，但其实树剖的原理非常简单，下面先说树剖大概的实现思路和解决题型。 概览 其实树剖就是把一棵树分成若干条链，使得每个点都出现在了刚好一条链上。 并且，我们称在某条链上的边为“重（zhòng）边”，不在任何一条链上的边为“轻边”。 然后，我们按某种规则去DFS，求出新的DFS序，然后解决对树上路径询问的问题。 而且，通过合理的设计每条边的轻重，可以把复杂度控制在 $O(\log n)$ 级别。 解决题型 上面也提到了，树剖就是用来解决对树上路径进行询问的问题的算法，当然也可以解决对子树询问的问题，不过属于大材小用了。 此外，树剖属于工具类算法，所以往往会配合树状数组、线段树、分块等算法出现。 我把算法分为了两类，“材料类算法”和“工具类算法”，其中： 材料类算法可以单独考，比如： 数论 推公式 DP 树状数组 线段树 … 工具类算法里面必须要套材料类算法才能考出来，比如： 二分 01分数规划（二分的一个分支） CDQ分治（需要配合树状数组） 整体二分（需要配合树状数组） 树剖（这里讲的） … 往往一些较难的题目，都是要用较难的材料类算法（比如DP），或者工具类算法配合材料类算法才能解决的题目。 而对于后者，难度会更大一些，因为后者的关键在于转化后使用工具类算法解决。 算法实现 下面说一下树剖的实现。 两遍DFS 我们考虑DFS，当递归到点 $x$ 的时候，找到 $x$ 的儿子中，子树大小最大的那个儿子 $to$。 然后，我们把 $x \to to$ 这条边设为重边，其他边设为轻边。 得到每条边的轻重后，我们再做一遍DFS。 而这一遍DFS是为了找到DFS序。 而且，DFS序有一个要求，我们要先遍历有重边连接的儿子。 这样的话，对于任意一条树上的链，链上所有点的DFS序连续，而且是由深度从浅到深依次递增。 同时，我们还要求出，从一个点开始，不经过任何轻边，最多到哪个点。 解决询问 而对于一次路径上某值的询问，我们可以把这个路径拆成若干条链。 可以证明链数不超过 $O(\log n)$，这一点会在下面“复杂度证明”中证明。 而这些拆出的链，都是原树中的链的“子集”（一条链 $L_1$ 是另外一条链 $L_2$ 的子集，有且仅当 $L_1$ 中的点，$L_2$ 中也有，边同理）。 所以，可以把一条路径，拆成最多 $O(\log n)$ 个DFS序区间。 ...

（四边形不等式看标题可能觉得很难，其实比较简单） 四边形不等式是一种DP优化的技巧，一般针对二维DP进行优化。 在DP中，往往会有多个决策点，而其中就有一个是最优的，设 $d_{i,j}$ 的最优决策点为 $f_{i,j}$。 （以下假设DP枚举决策点的复杂度为 $O(n)$，DP状态数为 $O(n^2)$） 而四边形不等式就是说，如果满足 $f_{i,j-1} \leq f_{i,j} \leq f_{i+1,j}$，那么可以把DP枚举决策点的范围降至 $[f_{i,j-1},f_{i+1,j}]$，然后DP的复杂度就从 $O(n^3)$ 降到了 $O(n^2)$。 而这个（复杂度）怎么证明呢？我们画一下 $f$ 数组的表： （此处，我们以 $i$ 为行号，以 $j$ 为列号，行、列号都从 $1$ 开始编号） 然后，画几个标记： 这些标记指的是，在转移 $d_{1,2}$ 的时候，转移点枚举的左右端点分别就是红箭头指向的两个数。 同时，为了方便观察，此处还画了个蓝色的虚线。 同理，还可以画出 $d_{2,3}$ 对应的标记： 以此类推： 可以发现，其实这时候所有蓝线的长度（蓝线连接的两个数字的差值定义为这个蓝线的长度）之和，最多只有 $n$。 而对于 $d_{1,3}$ 一“类”的标记： 可以发现，其实那些蓝线的长度之和也是最多只有 $n$。 在画出所有蓝线之后： 可以发现，一共就有 $n$ “类”蓝线，一“类”蓝线的长度之和最多 $n$，至此，可以证明复杂度（所有蓝线的长度之和）为 $O(n^2)$。 接下来讲几类四边形不等式解决的经典题型： 第一类：$d_{l,r}=\min { d_{l,k}+d_{k+1,r} | l \leq k \leq r }+w_{l,r}$，合并石子类。 第二类：$d_{i,j}=\min { d_{k,j-1}+w_{k+1,i} | 0 \leq k \leq i }$，区间分割类。 （这两类对应的公式里的 $\min$ 也可以替换成 $\max$） ...

同余最短路看名字感觉很难，但其实非常简单，也好理解，先说一道题： 题目 原型：洛谷P3403 跳楼机 有一栋 $h$ 层的大楼（层数编号从 $1$ 到 $h$），有 $n+1$ 种移动方式： 回到 $1$ 层 向上走 $x_1 \sim x_n$ 层 楼层不是循环的，你无论如何都无法到达 $h+1$ 层或以上。 最初你可以在任意一层（但也无关紧要），问你能到达多少个不同的楼层。 题解 分类 我们按楼层模 $x_1$ 的余数分类，把楼层 $i$ 分到 $i \bmod x_1$ 类。 这样分类有什么用呢？见下。 定义状态 有了这个分类，我们可以定义状态 $d_i$（$i \in [0,x_1)$）代表不用「向上走 $x_1$ 层」操作能到达的、最小的第 $i$ 类楼层是多少。 那么，由于有「向上走 $x_1$ 层」操作，所以 $d_i,d_i+x_1,d_i+2x_1,\dots$（比 $d_i$ 大或相等的第 $i$ 类楼层）都是可达的。 接下来考虑转移这个状态。 转移 其实也很好想，比如用一次「向上走 $x_2$ 层」操作，那么 $d_i$ 可以转移到 $d_{(i+x_2) \bmod x_1}$，转移代价为 $x_2$，所以： $d_{(i+x_2) \bmod x_1}=\min(d_{(i+x_2) \bmod x_1},d_i+x_2)$ ...

要说行列式，就得先说一下矩阵（其实是方阵）的秩的定义。 对于一个方阵，其秩的定义就是矩阵里线性无关的极大值。 听这个定义有点难懂，这里解释一下。 其实一个方阵就可以被当做是一个没有右项的方程集。 而一个方阵的秩就可以当做是，这个没有右项的方程集在经过高斯消元后，非 $0$ 行的数量。 有了这个定义，矩阵的秩还可以被当做是，这个没有右项的方程集中，不会被其他方程替代掉的方程数量： 解释一下，如果方程长这样： $ \begin{cases} -x_1+2x_2+5x_3=11 \ 2x_1=8 \ x_1+2x_2+5x_3=19 \end{cases} $ 那么，其实第三个方程式可以通过前两个方程式推出来，也就称作第三个方程式可以被前两个方程式替代掉。 知道了“替代”的定义后，就知道了一件事，就是上面说的“会被其他方程替代掉的方程”，这些方程可以直接从方程组里去掉，而不影响最终的解。 所以，我们就可以对奥数里的一个点做一个更简洁的解释： 在奥数里，讲了解 $n$ 元一次方程（组）的方法。 同时还说了，在这个 $n$ 元一次方程组内，如果“有用”的方程数量，刚好等于未知数的数量，或者大于未知数的数量，那么这个方程组就有唯一解。 这一点可以被更简洁地解释为： 这个 $n$ 元一次方程组，转化为“高斯矩阵”，并删除最后一列后（变成 $n \times n$ 的方阵），如果这个方阵的秩刚好为 $n$，那么这个方程组就有唯一解。 然后，我们回归正题，说行列式。 行列式是对于一个方阵来讲的，一个方阵有行列式有且仅当这个方程的秩刚好等于方阵的大小（行或者列）。 行列式的定义此处不讲，因为： 太复杂了 （几乎）没有用处 行列式的计算方法是用的高斯消元。 在高斯消元的思路里，提到了三种“基本行变换”：（以下全部以高斯矩阵的角度去说） 将一行全部乘上一个非 $0$ 实数 $x$，解不变。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，解不变。 交换两行，解不变。 这三种基本行变换在执行前后，行列式并不是都不变的： 将一行全部乘上一个非 $0$ 实数 $x$，行列式也会乘上 $x$。 将一行内的所有元素对应地加上/减去另一行对应的元素乘上一个非 $0$ 实数 $x$，行列式不变。 交换两行，行列式变号（负数变成正数，反之亦然）。 所以我们只用写一下高斯消元，然后处理一下对行列式的值的变化即可。 但这儿还有一点问题，就是行列式怎么求。 求法很好记，如果说当前方阵是个上三角矩阵（设方阵叫 $a$，那么 $a$ 是个上三角矩阵有且仅当对于所有的 $(i,j)$，如果满足 $i>j$，那么 $a_{i,j}$ 一定要等于 $0$，当然其他方格不做要求），那么这个方阵的行列式就是这个方阵中正对角线上的元素的乘积。 ...

说一个非常重要的语法错误。 如果你写这样一句话： v[x] = newnode(); 其中： v为一个vector。 x为不越界的非负整数，且不会变化。 newnode()函数内会向vector内push_back一个新元素，并返回加入元素（即最后一个元素）的下标。 那么，你会发现，v[x]的值并不是这样变化的： 1,2,3,4,5,6,7,... 而是类似于这样的：（非真实输出结果，仅供参考） 1,1,2,2,3,4,4,5,6,7,8,8,9,10,11,12,13,14,15,16,16,17,18,19,20,... 你会发现部分情况下，v[x]没有变化！ 这实际上是因为vector的内部机制。 vector会有一个capacity，就是提供的内存大小。 每次push_back的时候，如果说加入后，不超过当前的capacity，就会直接加入。 否则，vector会新开辟一块等于当前capacity的两倍（这个在不同编辑器上是不一样的，有些可能是每次新增 $5$ 个）的新空间，并把原本的数据拷进这块新空间内。 比如说现在的vector是： 内存354~357位置：3 1 2 4 且capacity是 $4$，那么我们如果尝试push_back一个 $5$，则vector就会发现大于了capacity，便会新开一块等于当前capacity的两倍的空间： 内存354~357位置：3 1 2 4 内存382~389位置： 并把当前数据拷进去： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 然后在新空间内加入 $5$： 内存354~357位置：3 1 2 4 内存382~389位置：3 1 2 4 5 并把所有v[x]指向的内存都改成382~389这块新内存内对应的地方。 不过由于C++的赋值机制，系统会先找到要赋值给的变量的指针，然后求出要赋的值，赋给以前找到的指针。（这一步是推测，可能不准确） 所以就会导致把newnode()的值赋给了原本的v[x]，导致输出的时候访问的新v[x]值出错。 解决方法也很简单，把newnode()用个临时变量t存储，并将v[x]赋值为t即可。

在数学、编程界里，可能会经常遇到方程，而且有时候还会遇到一种特殊方程——一元二次方程。 除此之外，还有含参一元二次方程，这里也会一起讲。（待补充） 其实还有如二元一次方程、一元三次方程等的特殊方程，但在这里不讲。 一元二次方程 有人看到“一元二次方程”就不知道是啥意思，这里先说一下定义 定义 首先，方程相信大家都见过，所以这里不写对方程的定义解释。（废话 而 $x$ 元 $y$ 次方程就是这么定义的： 这个方程经过化简后，共有 $x$ 个未知数，且未知数上的最大指数为 $y$ 的方程。 如： $3(x+1)=6x$：一元一次方程，也是最常见的方程。 $3(x+1)^2=2(x+1)$：一元一次方程，因为两边可以同时除以 $x+1$ 以让指数减少 $1$。 $x^2-4x+1=0$：一元二次方程，也是下面要讲的方程类型。 $x^3+2x^2-1=16x$：一元三次方程，也是一种不常见的方程类型。 讲完定义，接下来说怎么解 解法 推导 我们把方程一般化，变成： $ax^2+bx+c=0$ 其中 $a$、$b$、$c$ 均为常量。 然后，我们不断对方程做一些推导。 移项 $ax^2+bx=-c$ 同时除以 $a$ 常量 $x^2+\dfrac{b}{a}x=-\dfrac{c}{a}$ 这个式子很多人看了就不知道怎么继续推导了。 但还是可以继续转化的。 我们考虑配方，即把式子的左/右项同时加/减/乘/除一个相同的数，然后让这个等式的左/右项变成一个数的平方的形式。 这一步比较考验数感，一个结论就是，我们同时加上 $\left( \dfrac{b}{2a} \right)^2$ 常量 即可。 $x^2+\dfrac{b}{a}x+\left( \dfrac{b}{2a} \right)^2=-\dfrac{c}{a}+\left( \dfrac{b}{2a} \right)^2$ 化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{-c}{a}+\dfrac{b^2}{4a^2}$ 二次化简 $\left( x+\dfrac{b}{2a} \right)^2=\dfrac{b^2-4ac}{4a^2}$ 同时开根号 $x+\dfrac{b}{2a}=\sqrt{\dfrac{b^2-4ac}{4a^2}}$ ...