标签：总结 知识点 log NOIP 复杂度 可以 例题 线段 dp

NOIP知识点总结

基础算法

模拟/搜索

• 最基础的东西。
• 没有思路就要打暴力！
• 写模拟注意思路清晰。
• 例题：[CSP-S 2023] 结构体，[NOIP2017 提高组] 时间复杂度。应该不会有更难的模拟了吧？

分治

• 将问题分为子问题，分别解决，然后再合并。
• 归并排序利用了分治思想。

贪心

• 需要证明，最好不要乱写。
• 没有思路的时候可以考虑一下有没有可能是贪心。
• 例题：[NOIP2012 提高组] 国王游戏。

排序

• 方法很多，但大部分时候 sort 就够用了。
• 主要的考察方式可能是排序的内部思想，比如冒泡排序与逆序对。

前缀和 & 差分

• 比较基本的转化方式，用来进行区间和单点间的转化。
• 可以上树，能优化很多东西。
• 能做高维前缀和。
• 前缀和例题：[NOIP2022] 种花。
• 差分例题：[NOIP2021] 方差，[NOIP2016 提高组] 天天爱跑步。

二分

• 常用于求最大/小值最小/大。
• 将问题转化为判定性问题。
• 可以用于查找。
• 例题：[CSP-S 2023] 种树，[NOIP2018 提高组] 赛道修建。

倍增

• 最知名的应用应该是倍增求 LCA。空间复杂度一般要带 \(\log\)。
• 例题：[NOIP2012 提高组] 开车旅行。

数据结构

线性结构

• 包括栈，队列，链表。
• 支持 \(O(1)\) 插入/删除。
• 单调队列/单调栈就是元素满足单调性的队列/栈。可以在上面二分，或者维护一些信息，如序列中第一个 \(>a_i\) 的数。有的时候题目本身的性质就满足了单调性，如 [NOIP2016 提高组] 蚯蚓， [CSP-S2020] 贪吃蛇。

哈希

• 哈希表支持 \(O(1)\) 插入/修改，一般使用拉链法实现，也可以使用 map/unordered_map 实现。后面的一般是够用的，除非需要卡常。
• 可以利用哈希来解决判等问题，如 [NOI2024] 集合，[CSP-S 2023] 消消乐。
• 可以通过构造一个容易判定的必要不充分条件，利用哈希随机赋权来提高正确率。如 [CSP-S 2022] 星战。

并查集

• 用于判断两个元素是否属于同一集合。可以用于维护图的连通性等信息。
• 按秩合并：将大小（深度）的并查集合并到大的并查集上，复杂度 \(O(\log n)\)。加上路径压缩复杂度是 \(O(\alpha (n))\) 的，其中 \(\alpha (n)\) 为反阿克曼函数，可以近似认为是常数。
• 带权并查集：对于并查集的边定义一定的权值，并且定义其在路径压缩时产生的运算，就可以在并查集中维护一些信息，例如深度/权值等。
• 扩展域并查集：一个节点可能有很多状态，对于每个状态开一个并查集。如 [NOI2001] 食物链。
• 可撤销并查集：记录合并时的操作/合并前并查集的权值。不能路径压缩！
• 并查集能可持久化。

ST 表

• \(O(n\log n)-O(1)\) 解决区间最值问题。也可以用于维护一些可重信息，比如 \(\gcd\)。

二叉堆

• 支持 \(O(\log n)\) 插入，\(O(\log n)\) 删除最值，\(O(1)\) 查询最大值。一般用 priority_queue 实现，但注意这是大根堆。

左偏树

• 在二叉堆的基础上支持 \(O(\log n)\) 合并操作。

树状数组

• 支持 \(O(\log n)\) 插入，查询。维护的信息需要满足可减性，例如区间和。
• 可以维护前/后缀信息，如最值。
• 相比线段树，优势在常数较小。
• 树状数组上也可以二分，实现方式类似于倍增。例题：[NOIP2017 提高组] 列队，当然 \(\log^2 n\) 也能过。

线段树

• 应该是 NOIP 以下最难的数据结构。
• 线段树维护的信息需要可以快速合并，并且满足封闭性（个人理解是不需要引入外部信息来维护线段树内信息）。如区间最值，区间和。
• 支持 \(O(\log n)\) 的修改及查询。
• 线段树信息设计：一般来说，线段树上的信息分为信息（\(D\)）与标记（\(M\)）。其中 $M $ 是线段树能够保证复杂度的核心。在设计信息时，可以先列出一些必要的信息，再导出更多的必要信息。在考虑信息与标记间转化时，需要考虑 \(D\times D\)，\(D\times M\)，\(M\times M\)（此处的 $\times $ 代表某些神秘操作）。例题：P4314 CPU 监控。

动态开点线段树

• 由于点数过多，无法先把树建出来，但是需要用到的点较少，因此在用到时开点。空间复杂度 \(O(Q\log V)\)，\(Q\) 为操作次数，\(V\) 为值域。

可持久化线段树

• 由于线段树一次只会修改 \(O(\log n)\) 个节点，我们可以只更新变化的节点，从而保存历史版本。空间复杂度 \(O(n\log n)\)。
• 不好 Pushdown，因此可能要改成单点修改或标记永久化。

扫描线

• 可以维护二维平面上与矩形有关的一些信息，比如矩形大小，面积。实现方法为用一条线从下往上扫，同时将将矩形贡献在下边界插入，上边界删除。

• 可以标记永久化。

• 可以将问题抽象到二维平面上，比如把对满足某些条件的 \((x,y)\) 进行修改转成矩形修改操作。

• 也可以被称为一种思想，在枚举位置的时候加入/删除贡献。

• 例题：[春季测试 2023] 密码锁。非常难写。

线段树二分

• 可以在线段树上利用节点本身的权值进行二分，因为线段树的结构本身就很适合二分。

标记永久化

• 不将标记下放，而是在询问时考虑懒标记。不会带来复杂度的优化。一般会与不好下传标记的线段树配合使用（如可持久化线段树）。

历史和线段树

• 在维护线段树的过程中维护所有历史版本的和。如 [NOIP2022] 比赛。

线段树合并

• 支持合并两棵动态开点线段树。一般可以代替启发式合并。
• 合并 \(n\) 棵有一个元素的线段树复杂度为 \(O(n\log n)\)。复杂度是均摊的。
• 可以支持撤销。
• 真的会考。[NOIP2021] 棋局也干了。

李超线段树

• 能够维护与线段有关的问题。一般用于斜率优化的维护。

兔队线段树

• P4198 楼房重建
• 维护前缀最大值一类的信息，需要单边递归，单次操作复杂度 \(O(\log^2 n)\)。如 [省选联考 2024] 最长待机。

其他技巧

• 可以用矩阵的形式表述线段树上信息的转移。这样会带大常数，可以先用矩阵的方式写出来，再手动去掉无用的状态。

二叉搜索树

• 是一棵二叉树。
• 满足一个点的权值大于其左儿子的权值且小于其右儿子的权值。

平衡树

• 是保证深度为 \(O(\log n)\) 的二叉搜索树。

• 支持 \(O(\log n)\) 插入/删除/查询排名，也可以维护一些其他信息。

• 可以维护区间信息，如平移/翻转。

• 本质上是二叉搜索树。

• NOIP 应该不会考，所以没有深入研究。

笛卡尔树

• 我们为每个点赋予一对键值 \((k,w)\)，令 \(k\) 满足二叉搜索树的性质，\(w\) 满足堆的限制，那么建出来的就是笛卡尔树。常将数组下标作为 \(k\)。
• 可以做到 \(O(n)\) 建树。

分块

• 主要思想：将序列分为若干个块，对于区间修改/查询操作将其分为整块和散块分别处理。
• 需要平衡复杂度。
• 例题：[NOI2020] 时代的眼泪，Ynoi 系列的大部分题目。
• 理论上也不会考。

莫队

• 将序列分块，以左端点所属块为第一关键字，右端点为第二关键字排序。然后暴力做。
• 有很多衍生出来的神秘科技，Ynoi 中亦有记载。
• 理论上更不会考。

图论

BFS/DFS

• 对图进行遍历。
• BFS 能 \(O(n)\) 地求边权为一的图的单源最短路。
• dfs 树有一些能够利用的性质，之后会提到。

树

定义

• 无向无环图/有 \(n-1\) 个结点的联通无向图/任意两个结点之间有且仅有一条简单路径的无向图。
• 也存在有向树。

树的直径/中心/重心

• 了解求法。直径可以两次 dfs/树形 dp，中心/重心可以记录深度/大小后求。

最近公共祖先 (LCA)

• 倍增：\(O(n\log n)\sim O(\log n)\)。可以将倍增数组中小的一维放在前面来卡常。
• 树剖：\(O(n)\sim O(\log n)\)，常数比倍增小一些。
• 欧拉序转化为 RMQ：\(O(n\log n)\sim O(1)\)，用 st 表实现。也可以用 dfs 序，常数小一些。
• Tarjan+并查集：离线求 LCA，复杂度 \(O(m\alpha(n))\)。也可以线性实现。

树链剖分

• 优雅的暴力。
• 重链剖分是将按照子树大小划分轻重儿子，长链剖分是按照子树深度。下文的树链剖分默认为重链剖分，因为我没怎么研究长链剖分。
• 一个点到根的路径上最多只有 \(\log n\) 条重链。因此，我们可以某些数据结构来维护链上的信息。例如，由于我们可以通过重标号使得一条链的编号连续，就可以利用线段树的数据结构来维护区间信息了。不算线段树复杂度是单次 \(O(\log n)\) 的。

虚树

• 适用于树上点很多，但是关键点很少的情况。将所有关键点及两两之间的 LCA 拉出来构建信息，并保存原树上的信息。具体构造过程可以排序后求相邻点之间的 LCA。因此虚树上的点数是 \(O(n)\) 的。
• dp 中也会用到，如 [SDOI2011]消耗战。
• 应该不会考。

基环树

• 在树的基础上增加了一条边，从而形成了一个环的图。
• 突破点一般在环上。
• 例题：[NOIP2018 提高组] 旅行，[NOIP2023] 三值逻辑。

点分治

• 对于原问题，我们将其分为经过点 \(x\) 和不经过 \(x\) 两种情况来考虑。例如，我们要求出是否存在长度为 \(a\) 的路径，就可以将路径按照是否经过 \(x\) 分类，然后删掉 \(x\)，将树分为多个更小的子树考虑。
• 我们每次挑选出树的重心能使递归层数最少，复杂度（包括遍历）为 \(O(n\log n)\)。

拓扑排序

• 只能在有向无环图（DAG）上使用。
• 每次取出入度为 \(0\) 的点，然后更新其所有出边能到达的点的入度。复杂度 \(O(n)\)。
• 例题：[NOIP2020] 排水系统。

最小生成树

• Prim：我们记录每个点与所选点集中的点的最短连边的长度 \(d\)，每次取出 \(d\) 最小的点，然后利用其更新。复杂度 \(O(n^2)\)，可以在稀疏图中利用堆优化至 \(O(m\log m)\)。
• Kruskal：将边按照边权排序，每次试图加入一条新边，若其连接的两个节点属于同一个连通块内，那么加入该边。复杂度 \(O(m\log m)\)。
• 例题：[NOIP2013 提高组] 货车运输。

Kruskal 重构树

• 我们在将两个节点所处连通块合并时，建出一个虚点连到这两个连通块上。
• 性质：我们将新加入的边的边权作为虚点的点权，那么两个点的 LCA 的点权就是他们在最小生成树上的路径上边权的最大值，并且点到根节点这条路径上的权值单调递增。例题：[NOI2018] 归程。

最短路

• Floyd：全源最短路，复杂度 \(O(n^3)\)。非常好写。
• Dijkstra：单源最短路，复杂度 \(O(n^2)/O(m\log m)\)，后者使用堆优化。是稳定的基于贪心的算法。
• Bellman-ford：单源最短路。直接将全部边松弛 \(n\) 次，复杂度 \(O(nm)\)。可以跑负权图，可以判负环。
• SPFA：Bellman-ford 的队列优化版本，但是复杂度最差仍然是 \(O(nm)\)。可以用于判负环，在随机图上表现优秀。关于 SPFA，它死了。
• Johnson 全源最短路：先跑一遍 Bellman-ford，再重新定义边权，跑 \(n\) 轮 Dijkstra。复杂度 \(O(nm\log m)\)。

差分约束

• 解形如 \(x_a-x_b\le y\) 的不等式组，利用大于关系连边，再跑最短路。
• 我只打过板子。

同余最短路

• 可以解决形如"至少要拼几次才能拼出模 \(m\) 余 \(p\) 的数"的问题。
• 例如“给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最大的整数”。我们以第一个元素为基准，然后在模这个元素的意义下做这个问题。那么，对于大小为 \(x\) 的元素，我们可以对 \(y\to (x+y) \bmod a_1\) 连边，点 \(p\) 的点权为所能拼出的模 \(a_1\) 意义下为 \(p\) 的最小数。跑最短路即可。
• 你的同余最短路又何必是最短路？可以参考 Alex_wei 大神的“同余最短路的转圈技巧”。

Tarjan

• 可以用于求强连通分量，点双连通分量/割点/割边，边双连通分量。
• 注意几种算法代码实现的细微差别。

强连通分量

• 是有向图中的概念。
• 缩点之后的图是一张 DAG。
• 强连通分量的编号是合法拓扑序，在 2-sat 中有用。

点双连通分量

• 无向图中的概念。

边双连通分量

• 无向图中的概念。
• 缩点后是一棵树，这个性质可以使得在对边双缩点后转化为树上问题。如 [NOIP2022] 建造军营。
• 可以通过边双建出圆方树，但是 NOIP 应该不考。

2-SAT

• 先建出 \(2n\) 个点，分别表示第 \(i\) 个点为真/假的情况。我们对于每一种限制将其转化为「A 真/假则 B 真/假」的形式，然后通过连边关系表示推断。我们 Tarjan 缩点后，如果「\(i\) 真」和「\(i\) 假」在同一个强连通分量内则无解，否则有解。
• 应选择强连通分量编号较小的，不然可能会出现 A 能推出 B 但 B 不能推出 A 的情况。
• k-sat 问题在 \(k\ge 3\) 时属于 NP 完全问题，就是只能暴力的意思。
• 复杂度 \(O(n+m)\)，例题 [NOI2016] 网格。

二分图

• 能分成左右两部分，其中每个部分内部无连边的图。
• 匈牙利算法：求二分图最大匹配，复杂度 \(O(nm)\)，其中 \(m\) 为边数。
• 二分图最大匹配利用网络流做，复杂度 \(O(\sqrt n m)\)。
• 需要建模，例题 [CEOI2002] Royal guards。

网络流

• Dinic 算法复杂度 \(O(n^2m)\)，但是一般不会卡 Dinic。在特殊图上会快很多。
• 费用流：在求分层图的过程中将 BFS 求深度改为 SPFA 的最短路。
• 平面图转对偶图：用于网格图等特殊图，可以跑最短路求最小割。例题：[CSP-S 2021] 交通规划，[ICPC-Beijing 2006] 狼抓兔子。
• 网络流侧重于建模。
• 应该不考。

线段树分治

• 离线，将删边转变为加边，代价是多一个 \(log\)。
• 一般配合可撤销并查集使用。记得不要路径压缩。

其他技巧

• 优化建图：有线段树优化建图/前后缀优化建图/分块优化建图等等技巧，最核心的思想是建出连向一部分点的虚点，从而达到区间连边的效果。

动态规划

性质

• 最优子结构
• 无后效性
• 子问题重叠

记忆化搜索

• 要打记忆化搜索嘞！
• 一般来说是先打一个搜索，然后发现有很多重复访问的状态，就把这些状态记忆下来。
• 可以搭配 map 使用。
• 在直接转移过于困难是可以记忆化搜索，如 [NOIP2017 提高组] 逛公园。
• 在有很多冗余状态的情况下也可以记忆化，如 [AGC020E] Encoding Subsets。
• 用记忆化搜索实现数位 dp 非常方便。

背包 DP

0-1 背包

• 物品只能拿一次，有代价 \(w_i\) 与价值 \(v_i\)。
• 有转移 \(\max(f_i,f_{i-w_i}+v_i)\to f_i\)。
• 也有计数类型的 0-1 背包，转移为 \(f_i+f_{i-w_i} \to f_i\)。
• 注意转移顺序，是从大到小。
• 背包的状态与物品顺序无关，因此计数背包是可撤销的。这里的可撤销不仅仅是 0-1 背包，完全背包也可以。

完全背包

• 物品可以拿无限次。
• 转移方程同上，转移顺序是从小到大。
• 例题：[NOIP2014 提高组] 飞扬的小鸟。

多重背包

• 有 \(k_i\) 个物品。
• 二进制拆分优化：将一个物品拆成 \(1,2,4\cdots\) 为一组，转化为有 \(O(n\log k)\) 个物品的 0-1 背包。
• 单调队列优化：将 dp 数组按照 \(\bmod w_i\) 的值分为 \(w_i\) 组，对每一组进行单调队列优化 dp。

分组背包

• 每个组中选一件物品。
• 对每个组做一次 0-1 背包即可。

树形依赖背包

• 物品之间有依赖关系。
• 把一个物品和所有被其依赖的物品放到一起，对每一棵树做分组背包。
• 例题：[NOIP2006 提高组] 金明的预算方案。

区间dp

• 将问题转化成每个区间中的子问题，对每个区间求解。
• 转移方程的形式一般为 \(f_{i,j}=\max\limits_{k=i}^j\{f_{i,k}+f_{k+1,j}+val\}\)。
• 例题：[NOIP2003 提高组] 加分二叉树，[CSP-S 2021] 括号序列。

树形 DP

树上背包

• 在树上做背包。不是树形依赖背包。
• 朴素实现复杂度 \(O(nk^2)\)，用子树 \(siz\) 精细实现后复杂度 \(O(nk)\)，其中 \(k\) 代表背包容量。

换根 dp

• 先做一遍暴力的树形 dp 算出根位置的答案，再考虑将其某一个儿子作为根会对答案产生什么影响。

状压 DP

• 状态总数不是很多，一般为 \(O(2^n)\) 的级别，\(n\) 很小。
• 将状态压缩为整数，通过枚举集合来进行转移。例题：[NOIP2017 提高组] 宝藏，[NOI2001]炮兵阵地。
• 子集枚举的复杂度为 \(O(3^n)\)。
• 可能需要钦定转移顺序来方便转移，优化复杂度。比如钦定必须要转移到当前状态中的第一个 \(1\) 之类的。如 [NOIP2016 提高组] 愤怒的小鸟。
• 不一定会直接把状压的东西非常明显地写出来，而是隐藏在一个比较大的数据范围内。如 经典的 [NOI2015]寿司晚宴。

数位 DP

• 对数字进行 dp。
• 是计数类型的 dp，通常表现为对满足某个条件且 \(\le x\) 的数字计数。
• 我喜欢使用记忆化搜索实现。
• 例题： [NOIP2021] 数列。

动态 dp

• 也叫 ddp。一般在树上实现。
• 将链分为重链和轻链，将转移用矩阵写出来，用线段树维护区间矩阵乘积。查询树剖即可。对于修改，我们将转移分为从重儿子转移和从轻儿子转移，重儿子的转移写到矩阵中不用修改，轻儿子暴力改。这样复杂度是 \(O(\log^2 n)\) 的，可以做到 \(O(\log n)\)，但是前者一般够用。
• 例题：[NOIP2018 提高组] 保卫王国，[CSP-S 2022] 数据传输。

dp 优化

• 方式很多。

单调队列优化

• 一个人要是比你小，还比你强，那你就永远打不过他了。

• 对于点 \(x\)，如果能找到一个点比它更优且能覆盖更多转移，那么肯定可以弹出 \(x\)。

• 加入元素时，弹出队首过时决策，弹出队尾不优决策，从而维护单调性。

• 这里的队列是 deque，即双向队列。

• 例题：[CSP-S2019] 划分。

斜率优化

• 将转移方程写成 \(\dfrac{Y_j-Y_i}{X_i-X_j}\) 的形式，然后维护凸包。

• 存在 \(a_ia_j\) 这一类项时，不能用单调队列，可以考虑斜率优化。

• 例题： [HNOI2008] 玩具装箱。

• 大概率不会考。

slope trick

• 画出 dp 图像，大概率能用归纳法证明 dp 值的图像是一个凸包。

• 分析转移造成的影响，想办法维护图像，比如可以用 multiset 记录斜率的变化点。

• 说到凸包顺便说一下，其实应该不能考。

四边形不等式

• 对于形式为 \(f_{i,j}=\min\{f_{k,j-1}+val(k+1,i)\},k\in [0,i)\) 的 dp，如果满足 \(val(l,r)+val(l+1,r)\ge val(l,r)+val(l+1,r+1)\)，则称其满足四边形不等式。
• 能通过四边形不等式推出 dp 数组的转移点具有单调性，可以通过分治，直接利用单调性等方式进行优化。
• 也可以打表猜单调性。

数据结构优化dp

• 种类很多，需要根据具体情况选择合适的数据结构维护合适的东西。
• [CSP-S 2024] 染色 前缀和优化 dp。
• [NOIP2023] 天天爱打卡 线段树优化 dp。

矩阵加速

• 如果转移有大段的相同，可以考虑将转移用矩阵的方式写出来，然后通过矩阵快速幂得到最终的 dp 值。
• 广义矩阵快速幂可以解决最优化问题，即 \(c_{i,j}=\max\{a_{i,k}+b_{k,j}\}\)。
• 可以通过矩阵乘向量把复杂度从 \(O(Q\log ^3 n)\) 优化到 \(O(\log^3 n+Q\log^2 n)\)。例题：[NOI2020] 美食家。

其他

• 容斥原理：可以考虑容斥原理优化 dp。例题：[CSP-S2019] Emiya 家今天的饭，[省选联考 2022] 卡牌。
• 猜结论：很多 dp 不能直接做，需要通过猜一些结论来得到题目的性质/充要条件，从而转化为更好 dp 的形式。如 [春季测试 2023] 圣诞树，[NOIP2021] 方差。

字符串

字符串哈希

• 哈希的一种方式。
• 可能会被卡，如果时间充裕可以写双模数哈希。
• 二分+哈希可以用来替代 Manacher，当然后者也不难写。

字典树（trie）

• 可以用来查找一个字符串是否出现过。
• 是 AC 自动机的一部分。
• 01 trie 可以用来解决异或相关问题，如 [省选联考 2024] 魔法手杖。

KMP

• 可以 \(O(n)\) 求出 border，构建单字符串的 fail 树。
• 可以通过 fail 树加速匹配，复杂度 \(O(|S|+|T|)\)。
• 思想是在通过 fail 树加速的基础上，自己与自己进行匹配，从而一边构建 fail 树一边利用。

扩展 KMP（z 函数）

• \(O(n)\) 计算 \(s\) 的每个后缀与 \(s\) 的 \(lcp\) 长度。
• 思想是通过前面已经算出的部分来加速处理后面的部分，复杂度是均摊的。
• 感觉像是 KMP+Manacher。
• 例题：[NOIP2020] 字符串匹配，当然只是这题中的一部分。

AC 自动机（ACAM）

• 不是自动 AC 机。
• Trie+KMP：现将所有模式串建成一棵 trie 树，然后处理出每个节点的失配指针。
• 能够解决多模式串匹配问题，复杂度 \(O(|S|+|\sum||T|)\)，$|\sum| $ 是字符集大小。
• 优化：在匹配时不是一直跳 fail，而是利用拓扑排序在最后一起更新。
• ACAM 上 dp：可以在通过 AC 自动机的节点进行字符串 dp，甚至还可以套上矩阵优化。

Manacher

• \(O(n)\) 处理回文串。
• 思想是利用之前算出的信息加速计算，处理出 \(1\sim i-1\) 作为回文中心时最远的右端点，然后将对称的点的最长回文串长作为初值。
• Manacher 处理的是奇回文串，所以需要在相邻字符之间插入一个神秘字符，如 '#'。
• 通过对 Manacher 复杂度的分析，能发现字符串中本质不同的回文串只有 \(O(n)\) 个。

其他

• 总长为 \(n\) 的一组字符串，其中本质不同的串长只有 \(O(\sqrt n)\) 种。
• NOIP 考字符串真的考得很少。

数学

位运算

• 初赛喜欢考（
• 计算机的底层逻辑，卡常效果显著。

快速幂

• \(O(\log y)\) 计算 \(x^y\)。利用了倍增思想。

数论

辗转相除法

• \(O(\log n)\) 求 \(\gcd(x,y)\)。

质数

• 能够 \(O(\sqrt n)\) 判断一个数是不是质数。
• 有更厉害的方法，但我不会。
• 可以线性筛判断 \([1\sim n]\) 之内的数是不是质数。线性筛也可以筛欧拉函数，莫比乌斯函数。

数论分块

• 对于形如 \(\sum\limits_{i=1}^n f(i)g(\lfloor \dfrac{n}{i}\rfloor)\) 的式子，如果可以 \(O(1)\) 计算 \(\sum\limits_{i=l}^r f_i\)，那么就可以 \(O(\sqrt n)\) 计算上式。

裴蜀定理

• 关于 \(x\) 和 \(y\) 的同余方程 \(ax+by\equiv c\) 的充要条件是 \(\gcd(a,b)|c\)。

逆元

• 当 \(m\in Prime\) 时，有 \(a · a^{m-2}\equiv 1 \pmod m\)。
• 扩展欧几里得：对于 \(ax+by=1\)，我们求出 \(bx'+(a \bmod b)y'=1\) 的解，那么 \(x=y',y=x'-\lfloor\dfrac{a}{b}\rfloor y'\) 是一组合法解，递归即可。
• 线性求逆元：对于 \(1!,2!,3!\cdots n!\) 的逆元，我们求出 \(n!\) 的逆元，然后 \(inv(i!)=inv((i+1)!)\times(i+1)\)。
• \(inv(i)=(m-\lfloor\dfrac{m}{i}\rfloor inv(m \bmod i)) \bmod m\) 。

中国剩余定理（CRT）

• 解方程组 \(\begin{cases} x \equiv a_1 \pmod {m_1}\\x \equiv a_2 \pmod {m_2}\\ \ \ \ \ \vdots\\ x \equiv a_n \pmod {m_n}\end{cases}\)，保证 \(m_1,m_2\cdots m_n\) 互质。
• 先计算所有模数的积 \(m\)，对于每个方程，算出 \(b_i=\dfrac{m}{m_i}\)，并算出其在模 \(m\) 意义下的逆元 \(b_i^{-1}\)，再计算 \(c_i=b_ib_i^{-1}\)（不取模）。\(x=\sum\limits_{i=1}^na_ic_i \bmod n\) 为一组合法解。

扩展中国剩余定理（exCRT）

• 对于方程组 \(\begin{cases} x \equiv a_1 \pmod {m_1}\\x \equiv a_2 \pmod {m_2}\end{cases}\)，将其转化为不定方程 \(\begin{cases} x =m_1p+a_1\\x =m_2p+a_2\end{cases}\)，有 \(m_1p-m_2p=a_2-a_1\)，扩欧求解即可。

欧拉函数

• 记作 \(\varphi(n)\)，含义是 \(\sum\limits_{i=1}^n [\gcd(i,n)=1]\)。
• 设 \(n=\prod\limits_{i=1}^s p_i^{k_i}\)，且 \(p_i\) 为质数，那么有 \(\varphi(n)=n\times\prod\limits_{i=1}^s \dfrac{p_i-1}{p_i}\)。
• 欧拉函数是积性函数，即对于 \(\gcd(a,b)=1\)，有 \(\varphi(ab)=\varphi(a)\varphi(b)\)。
• 欧拉反演：\(n=\sum\limits_{i|n} \varphi(i)\)。

欧拉定理

• 若 \(gcd(a,m)=1\)，那么 $a^{\varphi(m)} \equiv 1\pmod{m} $。

扩展欧拉定理

• \(a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} & \gcd(a,m)=1\\ a^b & \gcd(a,m)\neq1 ,b<\varphi(m)\\ a^{(b \bmod \varphi(m) )+\varphi(m)} & \gcd(a,m)\neq1 ,b\ge \varphi(m) \end{cases} \pmod m\)
• 对于幂塔（即形如 \(c^{c^{c^{c}}}\) 的东西），可以利用扩欧证明其在 \(O(\log n)\) 层后值就不变了。例题：[六省联考 2017] 相逢是问候。

莫比乌斯函数

• \(\mu (n)=\begin{cases} 1&n=1\\0&x^2|n,x\in N\\(-1)^k&else,n=\prod\limits_{i=1}^k p_i,p_i\in Prime\end{cases}\)
• 莫比乌斯函数是积性函数。
• 莫比乌斯反演：\(\sum\limits_{d|n} \mu (d)=\begin{cases} 1&n=1\\0&n \neq 1 \end{cases}\)。

组合数学

排列组合

• \(A_m^n\) 表示从 \(n\) 个数中选 \(m\) 的排列数，有 \(A_m^n=\dfrac{n!}{(n-m)!}\)。
• \(C_m^n\) 表示从 \(n\) 个数中选 \(m\) 的组合数，有 \(C_m^n=\dfrac{n!}{(n-m)!m!}\)。也记作 \(\dbinom{n}{m}\)。

Lucas 定理

• \(\dbinom{n}{m} \bmod p=\dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}·\dbinom{n \bmod p}{m \bmod p} \bmod p,p\in Prime\)。

容斥原理

• \(\mid\bigcup\limits_{i=1}^n a_i\mid=\sum\limits_{T\subseteq [1,n]\bigcap N}(-1)^{|T|-1}\mid\bigcap\limits_{i\in T} a_i\mid\)。

错排

• \(D_n=D_{n-1}+D_{n-2}\)。
• \(D_n=nD_{n-1}+(-1)^n\)。

卡特兰数

• \(H_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}\)。
• \(H_n=\dfrac{H_{n-1}(4n-2)}{n+1}\)。

线性代数

• 写了一些用的比较多的东西。

矩阵乘法

• \(C_{i,j}=\sum\limits_{k=1}^n A_{i,k}+B_{k,j}\)。
• 广义矩阵乘法：就是把上面的 $\sum $ 和 \(+\) 换成别的东西。需要验证其是否合法，比如 \((max,+)\) 就是合法的。
• 满足结合律，不满足交换律。
• 可以解决递推问题，也可以解决一些图上的问题，比如定长的权值最大路径。

线性基

• 一般是异或意义下的线性基。
• 可以在线性基上贪心，比如说求出一组数的最大异或和。
• 构建方法有贪心法和高斯消元法，后者构建出来的线性基性质好一些。
• 支持 \(O(\log n)\) 插入，\(O(\log n)\) 查询，\(O(\log^2n)\) 合并。应该不支持删除。

高斯消元

• \(O(n^3)\) 解方程组。感觉是很符合思考习惯的算法。

矩阵求逆

• 在原矩阵旁边放一个单位矩阵，对原矩阵进行高斯-约旦消元，消元后右边的就是逆矩阵了。

博弈论-公平组合游戏

• 没有写其他博弈论的内容，因为我不会。

Nim 游戏

• \(n\) 堆石子，每堆 \(a_i\) 个，取最后一个石子的人赢。
• Nim 和：\(a_1\operatorname{xor}a_2 \operatorname{xor} a_3\cdots \operatorname{xor} a_n\)。如果 Nim 和为 \(0\) 那么先手输，否则先手赢。

有向图游戏

• 大部分的公平组合游戏都可以转换为有向图游戏。

SG 函数

• \(mex\) 函数：\(\operatorname{mex}\{S\}=\min\{x\} ,x\not \in S,x\in N\)。
• 将游戏在有向图上考虑。设 \(y_1,y_2\cdots y_k\) 为 \(x\) 的全部后继状态，有 \(SG_x=\operatorname{mex}\{SG_{y_1},SG_{y_2},\cdots,SG_{y_k}\}\)。
• 对于由 \(n\) 个有向图游戏组成的组合游戏，我们设起点分别为 \(s_1,s_2,\cdots s_n\)，那么这个组合游戏的起点的 \(SG\) 值为 \(SG_{s_1}\operatorname{xor}SG_{s_2}\operatorname{xor} SG_{s_3}\cdots \operatorname{xor} SG_{s_n}\)。
• 当且仅当一个状态的 \(SG\) 值不为 \(0\) 时，先手必胜。

杂项

离散化

• 减小值域范围，很多时候是题目的第一步转化。
• sort+unique+lower_bound 三件套离散化。

高精度

• 朴素实现是加减法 \(O(n)\)，乘 \(O(n^2)\)。高精除低精 \(O(n^2)\)。
• 例题：[NOIP2020] 排水系统，[NOIP2012 提高组] 国王游戏。

双指针

• 利用单调性，通过两个指针的移动来维护信息。
• 例题： [NOI2024] 集合。

0/1分数规划

• 一般是在外面套一层二分，然后转化为判定性问题。
• 例题：[HNOI2009] 最小圈。

珂朵莉树/颜色段均摊

• 用 set/list 来维护颜色段。
• 复杂度基于数据。随机数据下复杂度是对的。

CDQ 分治

• 利用分治计算前一半对后一半的影响。本身复杂度是 \(O(n\log n)\) 的，不过一般要套数据结构。
• 有很严格的偏序关系限制。

随机化

• 用于最优化问题。
• 随机选择一个序列/点之类的东西，然后转化为判定问题。通过多次的随机选择一个比较优的解。
• 在某些时候正确性是有保证的，比如随机个 \(40\) 次，那么有点落在重心子树内的概率很大。
• 不要以随机化为第一选择，在时间充裕，拿完该拿的分之后再做考虑。
• 例题：[春季测试 2023] 密码锁，随机化有 95pts。

模拟退火/爬山

• 区别在于模拟退火以较低概率接受劣解，概率随时间降低。爬山则是只接受更优解。
• NOIP 中感觉不是很实用，谨慎选择。
• 例题：[NOIP2021] 方差。

标签：总结,知识点,log,NOIP,复杂度,可以,例题,线段,dp
From： https://www.cnblogs.com/liulianll/p/18576914