Aly_

1.动态规划 DP

​ 状态；状态的转移。

​ 记忆化搜索：对一个状态搜索完毕后记下当前状态以便以后使用。适用于状态转移复杂的 DP。

区间 DP

​ 状态常为区间左右端点。

​ 四边形不等式：设 $f_{l,r}=\min(f_{l,i}+f_{i,r})+w_{l,r}$，若 $w_{l,r}$ 满足四边形不等式 $\forall l_1\le r_1 \le l_2 \le r_2,w_{l_1,r_1}+w_{l_2,r_2}\le w_{l1,r2}+w_{l_2,r_1}$，则有 $f_{l_1,r_1}+f_{l_2,r_2}\le f_{l1,r2}+f_{l_2,r_1}$。见【决策单调性】

背包

​ 状态形如“体积为 $V$ 时的最大价值”。可看做多项式。

​ 泛化物品：把背包看成整体，求和即背包卷积，取并即背包取 Max。

​ 无限背包顺着扫，0-1 背包倒着扫。

​ 多重背包：朴素算法暴力加入；二进制拆分。单调队列优化多重背包：在等差组内转移。具体地，考虑转移方程 $f_{i,j}\Leftarrow f_{i-1,j-kc}+kw$，对同一个 $c$ 的同一个等差组，转移是 “ 连续的 ”，而 $kw$ 可以拆成两个贡献差分的形式，其中一个只与 $i$ 有关另一个只与 $i-kc$ 有关，因此可做单调队列转移。

​ 背包方案数：多项式优化。加入一个物品等价于乘 $1+x^c$，加入一个无限物品等价于乘 $\frac{1}{1-x^c}$。

​ 分组背包：每个组开新背包转移。

树形 DP

​ 每个点一般记录其子树内的答案。换根 DP 记录反向联通块答案。长剖优化见长链剖分。

​ 树形背包：每个点开一个背包；上下界优化可降复杂度；有时可将父节点已有答案代入子节点计算后与父节点取并降复杂度；DFN 序优化。

状压 DP

​ 把一个状态组压为一个整数。

​ 状压做“对应关系”的题时，一般表示成 ” 前 $|S|$ 个数与 $\{ S\}$ 中的数对应 ” 的形式。

​ 质因子状压：大因子只有一个，小因子状压。

​ 插头 DP：不整行转移。保存状态为当前位置在 $(i,j)$ 时所有已记录状态的边界状态，即 “ 轮廓线 ”。

数位 DP

​ 一般转化为形如 “ $i$ 位的首位为 $j$ 的数字”的状态。类似字符串上 DP。

概率/期望 DP

​ 走到某点的期望或从某点走到某点的期望或从某点走到终点的期望。

​ DAG 模型；带重边带自环 DAG 模型；有向图模型用高斯消元。

矩阵加速

​ 用矩阵表示一组状态及其附属信息并倍增优化之。可重定义乘法但要有结合律。

​ 行向量乘法+倍增预处理+二进制分拆优化可降一次询问复杂度。

​ K 进制倍增优化：预处理出 $1,2,...,K-1,K,2*K,...,(K-1)*K,.....,(K-1)K^p$ 的值后 K 进制拆位+行向量乘法。

​ 动态 DP：根据朴素 DP 的转移，可列出一个关于 DP 状态及附属状态的组合状态（一般为矩阵）使转移满足乘法结合律。修改时在矩阵上暴力修改并全局查询即可。树上问题：链分治，每个点维护所有轻 / 虚儿子的 DP 并，从重 / 实儿子转移上来。可使用全局平衡二叉树。鸽

凸优化

​ 斜率优化：用平面上的点和直线表示一组状态及状态之间的转移。一般形式为一条直线在凸包上的切点。大多有形式：$DP[i]\Leftarrow f(i)+g(ij)+h(j)+DP[j]$。

​ 若具有单调性，可用单调栈 / 单调队列优化；都不具有单调性，可用平衡树优化。

​ 有时也可李超树。

​ 凸包和：定义两凸包的和包含所有形如 $(x_1+x_2,y_1+y_2)$ 的点，其中 $(x_1,y_1)(x_2,y_2)$ 分别是两凸包内的点。形状：两凸包所有的边极角排序后转一圈。位置：取某一维的两个最值点，以此确定和的位置。单侧凸壳合并可双指针线性解决。

2.数据结构 DS

链表

​ 每个节点记录其前驱/后继。

栈 / 队列

​ 栈：先进后出；队列：先进先出；双端队列：两边进两边出。

​ 单调栈 / 单调队列：可用于特殊情况下 $O(1)$ 维护最值信息。

​ 悬线法：单调栈特殊情形，从可行点向下悬线，左右单调栈。

​ 线段树维护：

Hash 表

​ $O(1)$ 查询。良好的 hash 函数应选用奇怪的质数。插入数据过多时碰撞概率会很大。

​ Hash 挂链：在每个 hash 表的节点记录所有 hash 值相同的插入数据集合。不可能碰撞但会增大复杂度。

并查集

​ 支持 $O(\alpha(n))$ 合并集合 / 查找元素所属集合。

​ 启发式合并（小的向大的合并）/ 按秩合并（浅的向深的合并）均可降复杂度为 $O(\log n)$；路径压缩（在一个点访问根的时候压缩路径）可降复杂度为 $O(\alpha(n))$。

​ 带权并查集：类似普通并查集。每个节点记录其到父亲的权值。路径压缩时更新。

​ 可持久化并查集不可路径压缩。

​ 离线后配合其它数据结构可支持一大类图上操作。

ST 表

​ 支持 $O(n \log n)$ 的时空建表；$O(1)$ 查询。信息需对重复不敏感。建表时设 $f_{i,j}$ 表示从 $j$ 开始长为 $2^i$ 的区间信息，倍增合并。查询时找到可以覆盖该区间的两个区间后直接合并。可处理一大类区间合并类问题。

​ Four Russians：对于长为 $n$ 的序列，每 $\log n$ 分成一块，每块建 ST 表，对全局所有块建 ST 表，同时每块维护前缀后缀。复杂度：$O(n)-O(\approx 1)$ 建立 - 查询。

树状数组

​ 支持 $O(\log n)$ 可差分信息的单点修改 / 前缀查询。常数小。是线段树的左半边。

​ lowbit(x)=x&(-x)。

​ 差分后可支持区间修改 / 单点查询 & 区间修改 / 区间查询。

​ 树上子树修改 / 单点查询：把树转化为 DFN 序列后一个子树对应一段连续区间 $[l...r]$，子树修改时差分为 $d_l++;d_{r+1}--$ 的形式，单点查询时转化为到根链后直接查询 DFN 序上对应前缀即可。

​ 区间修改 / 区间查询：保存一次函数，即后缀修改对前缀查询的贡献。

线段树

​ 支持 $O(\log n)$ 区间修改 / 区间查询。支持各种操作。空间 $4$ 倍。

​ 区间操作前要下放懒标记，区间操作后要合并子区间信息。

​ 静态线段树节点 $u$ 左儿子 $2*u$ 右儿子 $2*u+1$ 父亲 $\lfloor \frac{u}{2} \rfloor$。动态开点线段树若访问到 $0$ 要直接退出若访问到叶节点不能设置儿子。空间开销小。

​ 权值线段树：支持 $O(\log n)$ 插入 / 删除 / 查询排名等；$O(\log^2n)$ 查找第 $K$ 大（二分答案）。值域较大时需离散化。

​ ZKW 线段树：自底向上实现的线段树。建满二叉树。

​ 猫树：$O(n\log n)$ 次合并的时空建树；$O(1)$ 次合并处理每个询问。

​ 建树时在线段树每个节点保存该区间前缀后缀，查询时中点分治，找到对应位置即可一次合并处理询问。

​ 若要求询问总复杂度 $O(1)$，可堆式建树后 $O(1)$ 找 $LCA$。适用于合并复杂度较高的信息。

​ 为链上的点分树，对应分治技巧为猫树分治 / 中点分治，即链上点分治。

​ Jiry Tree：$O(\log n)$ 处理**区间取 $\min$：**记录区间最大值和次大值，若一次修改对最大值毫无影响则忽略，可覆盖最大值则覆盖最大值，否则暴力递归后合并。作标记时可直接修改该点最大值，下传标记时观察父节点最大值是否小于子节点最大值即可知是否有标记存在。实质为对区间最大值进行区间加减等操作（即，分离为区间最大值和非区间最大值分别维护）。

​ $O(\log n)$ 处理区间历史最值：对于区间加标记 $l$，额外维护标记 $t$ 表示在 $t$ 存在（从有值到被下放）的时间内 $l$ 达到过的最大值，下放时更新即可。其他标记类似。

​ Li-Chao Tree：$O(\log n)\sim O(\log^2 n)$ 处理一次函数集合在某点的最值问题，看是单点操作还是区间操作。对每个区间维护其优势线段表示该线段在区间中点处取最值。加入时和每个优势线段比较；查询时找到所有优势线段中在该点最优势的那一个。

​ 单调栈线段树：线段树维护区间单调栈。方法：每次上传信息时直接继承其中一个，对另一个作一次 “ 小询问 ”，具体地，记 $sol(u,l,r,x)$ 表示询问 $u$ 代表区间，只保留 $x$ 以上的单调栈信息；记 $s_u$ 表示 $u$ 左半边对右半边的某种影响；询问时发现只用递归一边，$O(\log n)$ 一个整区间；修改后上传标记时为维护 $s_u$，对 $u$ 的右子树作一次询问，复杂度 $O(log^2 n)$。

​ 线段树合并：$O(minsize*\log n)$ 将两个线段树合并。一般要求启发式合并。要求动态开点。线段树分裂：找到值域切口并加入新点使分裂出的线段树完整。

​ 四分树：平均优秀最坏单次线性查询的二维数据结构。方法是把平面按横中轴竖中轴四分直至每个象限只有一个数据点。

堆

​ $O(\log n)$ 支持插入/删除元素。$O(1)$ 查找最值。形态一般为完全二叉树，每个点的权值大于其子节点。

​ 堆合并（左偏树）：支持 $O(\log n)$ 合并的堆。对深度没有保证，但有性质左儿子的深度大于等于右儿子的深度。合并时把小根的树向大根右儿子合并并递归。

​ 配对堆：支持：$O(1-1-\log n-1)$ 插入-查找最值-删除最值-合并；$\Omega(\log\log n)\sim O(2^{2\sqrt{\log\log n}})$ 减小元素的值。

​ 形态为堆序多叉树。删除最值时把儿子两两合并。

平衡树

​ $O(\log n)$ 的插入 / 删除 / 查询排名 / 查找第 $K$ 大 / 查找前驱后继。形态一般为二叉搜索树，即中序排列权值有序的树。

​ 伸展树 Splay：以伸展 ( splay ) 操作维护树的深度平衡。摊还时间界 $O(\log n)$。

​ void splay(int x){for(;fa[x];rot(x))if(fa[fa[x]])rot((getp(fa[x])==getp(x))?fa[x]:x);}

​ 支持区间翻转操作：节点以序列位置为序，翻转时打懒标记并交换左右儿子（旋转之前要提前下放）。区间平移用两次区间翻转。可提取区间：先 splay 右端点，再 splay 左端点。

​ Treap：以随机赋 $w$ 的方式维护树的深度平衡。$w$ 需满足堆序。期望时间界 $O(\log n)$。

​ FHQ-Treap：无旋 treap。操作为分裂和合并。插入为单点与整棵树合并，删除时先分裂出左边右边再合并之。可提取区间：分裂左边右边。

​ 同样支持区间翻转操作。

​ 替罪羊树：引入重构操作：当当前节点的左右子树过于不平衡 （$size$ 之比超过阈值 $\alpha$）时直接中序遍历成序列然后重构。

​ 平衡树合并：启发式合并 $O(n\log^2 n)$。Finger-Search：对于 Splay，启发式地，将小树按中序遍历插入大树，复杂度 $O(n\log n)$。

珂朵莉树 ODT

​ 均摊 $O(\log n)$ 维护区间推平+区间复杂信息查询。以整段为元素插入平衡树查询即可。区间推平时弹出所有影响区间并插入新区间。如果有区间修改在随机数据下亦能保持优秀速度。

K-D 树

​ 建树 $O(n\log n)$；$K$ 维矩形查询 $O(n^{1-\frac{1}{K}})$（特别地，二维矩形 $O(\sqrt{n})$）；近邻查询 $O(玄学)$；圆查询 $O(?)$；基于类平面分治维护高维空间信息（一般二维）。

​ 若需要插入 / 删除可引用重构操作：当一个点的子树大小之比超过某阈值时重构子树。

​ 可 Leafy 也可不 Leafy。

位运算数据结构

​ 0-1 Trie：建树时顺次插入每个数，树高一般 $O(\log n)$，$n$ 为值域。处理位运算相关问题，例：查找一个数与给定数异或最大。全局异或标记：旋转左右儿子。鸽

​ 线性基：空间 $O(\log n)$。通过其中的数可以异或出原数组所有的数。构造方法：对于每个数从高位到低位插入，若该位不为 $0$ 则用它异或该数，否则将该数插入。最小线性基：鸽

可持久化数据结构

​ 对各时间点相似的数据结构整体信息压缩保存的数据结构。

​ 主席树 SIT：支持时间 $O(\log n)$ 空间 $O(n\log n)$ 压缩储存线段树单点修改历史版本。用于静态区间第 $K$ 大可得到一个单 $\log$ 解法：序列上从前往后加入并用主席树可持久化（序列位置变成时间轴），查找时找到区间左右端点的线段树，同时在两棵值域线段树上二分并差分。

​ 可持久化并查集：不带路径压缩。每次合并时使合并边带权，权值为当前时间。

​ 历史版本查询时在树上跳到的最大边权不超过历史时间的地方必形成完整树形连通块，此即为该历史版本当前点的并查集。

​ 适用于一大类图上问题。

​ 可持久化 FHQ：鸽

​ 可持久化 0-1 Trie：空间 $O(n\log n)$。对于每个操作新开时间点并尝试向前面的历史版本连边。可看作另一种可持久化值域线段树。解决序列位运算问题。

​ 可持久化可并堆：解决 $K$ 短路问题。鸽

​ 可持久化 ODT：记录每个段的断开、组合的时间点。鸽

动态树

​ 支持树上动态连边/删边的数据结构。

​ Link-Cut Tree：$O(\log n)$ 支持树上连边断边路径修改查询。是若干 splay 形态的实链，同一实链上的点按深度为关键字排序。应用：鸽

​ 操作：

int access(int x){int np=0;for(;x;np=x,x=fa[x])splay(x),son[x][1]=np,lctup(x);return np;}
void mkrt(int x){x=access(x),tag[x]^=1;}
int fndrt(int x){access(x),splay(x),lctdown(x);while(son[x][0])x=son[x][0],lctdown(x);return x;}
int split(int x,int y){mkrt(x),access(y),splay(y);return y;}
bool iscn(int x,int y){mkrt(x);return fndrt(y)==x;}
void link(int x,int y){mkrt(x),splay(x),fa[x]=y,lctup(y);return;}
void cut(int x,int y){split(x,y),son[y][getp(x)]=0,fa[x]=0,lctup(y);return;}

​ Euler-Tour Tree：鸽

​ Self-adjusting Toptree（SATT）：鸽

树套树

​ 数据结构嵌套。

​ 二维链表：用于 DLX。对于每个节点有其在横轴方向上的前驱和纵轴方向上的前驱。

​ 二维 ST 表：$O(nm\log n\log m)$ 空间，$O(nm\log n\log m)-O(1)$ 预处理-查询维护重复不敏感信息。一般形如 $ST_{i,j,k,l}$ 表示从点 $(i,j)$ 开始向上 / 右分别扩展 $2^k,2^l$ 的矩形区域的最值。倍增合并预处理，查询时找最多 $4$ 个二维区间合并。

​ 二维树状数组：$O(nm)$ 空间，$O(\log n\log m)$ 单次单点修改 / 二维前缀查询维护可减信息。常数小。查询 / 修改时直接二维循环遍历所有受影响点。可解决在线动态二维数点。

​ 二维线段树：$O(nm)$ 空间，$O(nm\log n\log m)-O(\log n\log m)$ 预处理 - 查询维护可并信息。外层线段树的节点为内层线段树。动态开点可大幅度缩小空间。可解决大值域在线动态二维数点。

​ 线段树套平衡树：$O(n\log n)$ 空间，$O(log^2 n)$ 时间解决动态区间查排名 / 前驱 / 后继，$O(log^3 n)$ 时间动态区间第 $K$ 大（二分答案）。线段树的每个节点保存 set。

​ 树状数组套主席树：$O(n \log^2 n)$空间，$O(\log n)$时间在线动态区间第 $K$ 大：树状数组每个节点维护线段树。修改时在所有能影响到的区间修改，共 $O(\log n)$ 个，查询时对区间左右端点前缀定位然后差分 + 线段树二分即可。

若干技巧

​ 差分 合并 启发式合并 分裂 分治 二分答案 维护标记 动态结构 可持久化 坐标轴转换 分块 倍增分块 重构 平衡规划 优化建图（隐式建图降空间） 反向考虑（点对询问贡献）二进制分组（2048）

3.字符串 Str

Hash

​ 一般采用把字符串转化为模意义下 26 进制数。可提取子串。一般用以判断两串是否相同。模数选取：奇奇怪怪大质数。双模数：孪生质数。

KMP

​ $O(n+m)$ 模式串匹配。可用 AC 自动机式方法实现，空间不变，时间常数略增加。鸽

​ 扩展 KMP：鸽

​ Borders：一个字符串的 Border 为一个子串满足既是其前缀也是其后缀。KMP 求出每个前缀的最长 Border。将一个前缀向其最长 Border 连边形成 fail/link 树，称为失配树，一个点的祖先为其所有 Border，且长度随深度递减。

​ 串周期：称 $p$ 为一个串 $s$ 的周期当且仅当 $\forall s[i]=s[i+p]$。$p$ 是其周期当且仅当 $|s|-p$ 为其 Border。周期引理：若 $p,q$ 为 $s$ 周期且 $p+q-\gcd(p,q)\le |s|$ 则 $\gcd(p,q)$ 为 $s$ 周期。周期结构：字符串 $s$ 的所有 $\ge \frac{|s|}{2}$ 的 Border 构成等差数列，$s$ 的所有 Border 构成 $\log |s|$ 个等差数列且值域不交。

Trie

​ 对于一个字符串集合，把所有字符串挂到一棵树上并压缩相同位置的相同边。可用于简单字符串查找。

​ 压缩 Trie：压缩所有二度点。这样对应边就代表了一个子串。

Manacher

​ $O(n)$ 处理一个字符串的所有回文串的相关信息。

​ 从左往右扫，记录当前所有发现的回文串中最右端点。扫到一个新字符时，若其在最右端点之外则暴力扩展，否则找到其关于最右端点回文串的对称位置，以它为中心的最长回文串长至少有那么多，再暴力扩展。

​ 只能记奇串。若要记偶串，可加入特殊字符。

​ 字符串中本质不同回文串数量是 $O(n)$ 的。

AC 自动机

​ **在 Trie 树上连 fail 边。**具体地，在 Trie 上 BFS，对于一个点，假设现在欲求其 fail，从它父亲的 fail 开始跳 fail，直到 fail 存在一条与它父亲到它的转移边相同的转移边时连它的 fail。

​ 用于多串的单模式串匹配，方法是走到一个节点若有当前字符的边就继续走下一个否则跳 fail 边直到可以走为止。

​ 一个点的 fail 连向其在串集中作为子串出现，且不等于自身的最长后缀。

后缀数组 SA

​ 鸽

​ 后缀平衡树：

后缀树 & 后缀自动机 SAM

​ $O(n)$ 压缩保存字符串的所有子串的数据结构。

​ 形态：DAG，前向边由一条主链与若干单点之间连边构成；link 边构成一棵以空串为根节点的树，每个点的父亲为它的一个后缀，称为后缀树。

​ 意义：每一条路径表示一个子串；每一个节点表示有相同 endpos（结束位置）的子串集合，其 len 表示该 endpos 集合对应子串中最长子串的长度；有着相同 endpos 的子串互为后缀关系，且长度在 $[L,R]$ 之间，每个长度恰有一个；点 $p$ 的 link 边连向不是该点 endpos 集合（包含该 endpos 集合）的最 “ 近 ” 点 $q$，有关系：$L_p=len_q+1,R_p=len_p$；主链上的每一个点表示原串的一个前缀，其 endpos 唯一即为该前缀位置，也为其 len。link 树为后缀树，是所有后缀的压缩 Trie（压缩二度点）。用节点位置和子串长度可唯一确定一个子串，方法是后缀树上倍增。

​ 构造方法：对于一个新点 $new$，把其 len 设为上一个点 $last$ 的 len+1，并把 $last$ 向它连边，从 $last$ 向前沿 link 边跃进并把该点连向 $new$ 直到发现一个该位置已经有边的节点 $p$ 已连向 $q$ 或跳到根。分情况：若跳到根则把新点 link 向根直接退出；若 $len_q=len_p+1$ 则把新点 link 向 $q$；否则复制点 $q$ 至 $r$，把 $q$ 和 $new$ link 向 $r$，不断从 $p$ 向前跃进，若发现一条到 $q$ 的边则把它改为 $r$。

​ 应用：模式匹配，求本质不同子串数（自动机上 DP，后缀树边长和），求每个位置的最长匹配（在自动机上走并维护当前最长匹配，若能走边则匹配长增加，否则对跳 link 后跳到的点的 len 取 $\min$），求公共子串和本质不同公共子串数，子串定位（树上倍增）等。鸽

​ 广义后缀自动机： $O(\sum n)$ 压缩保存字符串集合的所有子串的数据结构。方法是加入一个点 $new$ 时设其 $last$ 为它在该串中的前一个字符加入位置，Trie 上 BFS 构造。

​ 压缩后缀自动机：鸽

回文自动机 / 回文树 PAM

​ $O(n)$ 保存字符串所有回文子串的数据结构。注意建立时间为 $O(n\log n)$。

​ 形态：两棵树，一棵为所有奇回文串（奇树），一棵为所有偶回文串（偶树）。link/fail 边也构成树形结构。偶根的 link/fail 连向奇根。

​ 意义：根到每个节点的路径对应一个半回文串（向上取整），$len$ 代表当前节点的最长回文串长度，$link$ 代表当前最长串的最长后缀回文串位置（也可看做 $fail$ 失配边）。

​ 构造方法：初始为偶根 $0$（$len_0=0,link_0=1$）奇根 $1$（$len_1=-1,link_1=随便$），$last=0$。每次加入一个字符（位置为 $x$）从 $last$ 开始跳 $link$ 边，直到找到一个节点 $p$ 使得 $s[x]=s[x-len_p-1]$（即，可以正好接上一个回文串）则当前位置对应节点为 $p$ 的儿子。找 $link$ 时从 $link_p$ 开始跳 $link$ 边，过程和上面几乎相同。若没 $link$ 上则 $link=0$。

子序列自动机

​ 接受字符串的所有子序列的自动机。方法是对于每个位置，求出其后每个字符第一次出现位置。复杂度 $O(nC)$。

自动机理论

​ 确定性有限自动机 DFA：

Lyndon / Runs / 最小表示法等

​

4.数学 Ma

数论 A

​ 素数判断 / 质因数分解：暴力$O(\sqrt{n})$。预处理素数表可优化复杂度。代数群分解法。

​ Miller-Rabin：基于费马小定理和二次探测定理的质数判断法，单次检验复杂度 $O(n^\frac{1}{4})$。费马小定理：对质数 $P$ 有 $a^{P-1}\equiv 1\mod P(a<P)$。二次探测定理：对质数 $P$ ，$a^2\equiv 1\mod P(a<P)$ 解为 $a\equiv \pm1\mod P$。方法是取随机一数检测，并将其不断平方。最后如果平方完了还不是 1，就不是质数；如果平方中间的某个时刻出现了 1，也不是质数。

​ Pollard-Rho：大整数因式分解，复杂度玄学。先判断是不是质数，如果不是则生成伪随机序列 $a_0,a_1=a_0^2+c,a_2=a_1^2+c,\cdots$，然后求两两差并与待分解数 $P$ 求 $\gcd$，不是 $1$ 则分解成功，发现成环则分解失败，调整 $a_0,c$。Floyd 判环法：两个指针，一个速度为 $1$，一个速度为 $2$，相遇则恰好一个环。

​ 筛法：埃拉托色尼筛 $O(n\log\log n)$。线性筛每个数被最大质因数筛掉，可筛几乎一切积性函数。

​ 线性筛：向前枚举。若当前数从未被遍历，则为质数，最小质因子为自身。枚举所有小于当前数最小质因子的数与当前数相乘即得乘积的最小质因子。

​ 区间筛：对 $[L,R]$ 筛。方法是同时筛 $[1,\sqrt{R}]$，筛出每一个质数都同时更新 $[L,R]$ 中的数。（似乎）不可线性。

​ 最大公约数 GCD：

$\gcd(x,y)=\begin{cases}x,&x\mid y\\\gcd(y\bmod x,x),&x\nmid y\end{cases}\\\ \\ \gcd(x,y)*\operatorname{lcm}(x,y)=x*y$

​ 也可看做高维 min 卷积。

​ $O(n)-O(1)$ GCD：基于根号分治。设值域为 $n$，则一个数 $x$ 可被分解为 $x=abc$，其中至多只有一个数大于 $\sqrt n$ 且该数为质数，分解方法是求出 $x$ 的最小质因子 $p$ 和 $x/p$ 的分解，再乘上 $p$。预处理 $\sqrt n$ 内两两 GCD。求两数 GCD 时考虑其中一个数的因子分解，对于 $\sqrt n$ 内的因数运用一次辗转相除求出与另一个数的 GCD，对于质数直接判是否整除，为避免算重，另一个数需除掉当前 GCD。

​ 区间修改区间 GCD：$\gcd(x,y)=\gcd(x,y-x)$，差分后变单点修改。

​ exGCD：设有

$Ax+By=1$

递归计算

$Bx_1+(A\bmod B)y_1=1$

有

$x=y_1\\ y=x_1-\lfloor\frac{A}{B}\rfloor y_1$

​ **类 Euclid：**快速求解形如 $\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$ 一类式子（直线下的整点相关计数）的方法。求解方式大多类似于：

\begin{align*} f(n,a,b,c)&=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor \\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}1 \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[j\le\lfloor\frac{ai+b}{c}\rfloor-1] \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[j+1\le\lfloor\frac{ai+b}{c}\rfloor] \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[j+1\le\frac{ai+b}{c}] \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[cj+c-b-1< ai] \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[i>\lfloor\frac{cj+c-b-1}{a}\rfloor] \\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor) \\&=\lfloor\frac{an+b}{c}\rfloor n-f(\lfloor\frac{an+b}{c}\rfloor-1,c,c-b-1,a) \end{align*}

​ 当 a\ge c\or b\ge c 时，有

$f(n,a,b,c)=(n+1)\lfloor\frac{b}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+f(n,a\%c,b\%c,c)$

​ 复杂度 $O(\log n)$。

​ 万能 Eucild：

欧拉函数：小于等于 $n$ 与之互质的数的个数。积性函数。计算方法（可 Pollard-Rho 优化）：

$\varphi(p^k)=(p-1)p^{k-1}(p为质数)\\ \varphi(n)=n\prod\frac{p_i-1}{p_i}(p_i为n质因数)$

此外，有

$n=\sum_{d\mid n}\varphi(d)$

​ 二次剩余：可用 BSGS 求解。数量级：一半。Euler 判别法：$a$ 是 $P$ 的二次剩余当且仅当 $a^\frac{P-1}{2}\equiv 1\mod P$。鸽

​ **N 次剩余：**模为素数的情况下把两边化为原根的幂求解。求任意解：鸽

​ 模数任意：鸽

​ **原根：**数论意义下单位根。存在性：$P$ 存在原根当且仅当 $P=2,4,p^a,2*p^a$，$p$ 为奇素数。判定：$g$ 为 $P$ 的原根当且仅当 $g^x\not\equiv 1\mod P$，其中 $x$ 为 $\varphi(P)$ 非平凡因数。个数：$\varphi(\varphi(P))$。性质：原根的幂次构成与 $P$ 互质的全部剩余系。鸽

​ 整除分块：$O(\sqrt{n})$ 解决一类函数求和问题。所求函数需具有类似 $\lfloor \frac{n}{i}\rfloor$ 的形式使之只具有 $O(\sqrt{n})$ 个值域相同块。 块的范围：$r=\lfloor n/\lfloor \frac{n}{l}\rfloor\rfloor$。

​ 欧拉定理：

$a^{\varphi(p)}\equiv 1\mod p\ \ \ (\gcd(a,p)=1)$

​ 费马小定理：欧拉定理的特例。

$a^{p-1}\equiv 1 \mod p\ \ \ (p为质数)$

​ 扩展欧拉定理：

$a^b\equiv\begin{cases}a^{b\bmod \varphi(p) },&\gcd(a,p)=1\\a^b,&\gcd(a,p)\ne1,b<\varphi(p)\\a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,p)\ne1,b\ge \varphi(p)\end{cases}\mod p$

​ 中国剩余定理 CRT：计算同余方程组的解。对于模数互质的情况

$\{x\equiv a_i \mod p_i\}$

解为

$x\equiv\sum_i a_i*q_i*(q_i^{-1}(模p_i意义下))\mod P\\(P=\prod p_i,q_i=\frac{P}{p_i})$

​ 扩展 CRT：对于两个任意模数方程

$\begin{cases}x\equiv a_1\mod p_1\\x\equiv a_2\mod p_2\end{cases}$

转化为

$x=a_1+p_1x_1=a_2+p_2x_2$

后，可运用扩展欧几里得求解。解为

$x\equiv((\frac{p_1}{\gcd(p_1,p_2)})^{-1}(模\frac{p_2}{\gcd(p_1,p_2)})∗\frac{(a_2−a_1)}{\gcd(p_1,p_2)})(\bmod\frac{p_2}{\gcd(p_1,p_2)})∗p_1+a_1 \mod(\operatorname{lcm}(p_1,p_2))$

对于多个方程，两两合并。

​ 简单做法：取大的模数在小模数中枚举，可继续优化。

​ 大步小步法 BSGS（离散对数函数）：对于 $\gcd(a,P)=1$，现欲求

$a^x\equiv b\mod P$

中的 $x$。根号分治求解，记$B=\sqrt{P}$，预处理出$a^B,a^{2B},...,a^{\lfloor\frac{P}{B} \rfloor B}$插入 map，再对于$i<B$查询$a^{-i}*b$是否出现。复杂度 $O(\sqrt{P})$ 或 $O(\sqrt{P}\log P)$。

​ 扩展 BSGS：若不保证 $\gcd(a,P)=1$，则找出 $d_1=\gcd(a,P)$ 作变换 $\frac{a}{d_1}a^{x-1}\equiv \frac{b}{d_1}\mod \frac{P}{d_1}$，若 $a$ 与 $\frac{P}{d_1}$ 仍不互质就继续找出它们的最大公因数 $d_2$ 等直到它们互质，记 $D=\prod_{i=1}^k d_i$，有

$\frac{a^k}{D}a^{x-k}\equiv \frac{b}{D}\mod \frac{P}{D}$

于是逆元存在，即

$a^{x-k}\equiv\frac{b}{a^k}\mod\frac{P}{D}$

化为普通 BSGS。注意点：先枚举小于 $k$ 的 $x$ 是否有解；若发现新方程的一个解还要代回原方程看是否成立。

​ Lucas 定理：对于质数$P<n,m$，有

$\dbinom{n}{m}\equiv\dbinom{\lfloor n/P \rfloor}{\lfloor m/P \rfloor}\dbinom{n\bmod P}{m\bmod P}\mod P$

​ Lucas 的完全展开为把 $n,m$ 转化为 $P$ 进制后按位组合数之积。

​ 扩展 Lucas：计算 $\dbinom{n}{m}\mod P$ 的值，$P$ 不一定是质数。分解 $P$ 的质因数，分别计算 $\dbinom{n}{m}\mod p_i^{a_i}$ 的值，最后运用扩展 CRT 合并。有 $\dbinom{n}{m}\equiv\frac{n!}{m!(n-m)!}\equiv\frac{n!*p_i^{-x}}{m!*p_i^{-y}*(n-m)!*p_i^{-z}}p_i^{x-y-z}\mod p_i^{a_i}$，即，除去阶乘中的 $p_i$ 因子以便求逆元，最后乘回来。有

$n!\equiv p_i^{\lfloor\frac{n}{p_i}\rfloor}\lfloor\frac{n}{p_i}\rfloor!(\prod_{\gcd(j,p_i)=1}^{p_i^{a_i}}j)^{\lfloor\frac{n}{p_i^{a_i}}\rfloor}(\prod_{\gcd(j,p_i)=1}^{n\%p_i^{a_i}}j)\mod p_i^{a_i}$

​ 即：把 $n!$ 中所有是 $p_i$ 倍数的项提出来。分四部分：第一部分在乘 $p_i^{-x}$ 后被乘掉了，第二部分递归计算，第三、四部分是所有小于等于 $n$ 的数中与 $p_i$ 互质的数之积，在 $\mod p_i^{a_i}$ 下有模长度的循环节。暴力计算即可。

​ Kummer 定理：计算 $\dbinom{n}{m}$ 中质因子 $p$ 的次数。其等于 $n+m$ 在 $\mod p$ 加法过程中进位次数。

数论 B

​ 积性函数：若 $f(1)=1$，$\forall x,y\in N^+,\gcd(x,y)=1,f(x)f(y)=f(xy)$ 称 $f$ 为积性函数。若 $f(1)=1$，$\forall x,y\in N^+,f(x)f(y)=f(xy)$ 称 $f$ 为完全积性函数。

​ 常见数论函数：$\epsilon(n)=[n=1]$，$id_k(n)=n^k$，$\sigma_k(n)=\sum_{d|n}d^k$，$\varphi(n)$，$\mu(n)$。前两个完全积性。

​ 加性函数：$f(xy)=f(x)+f(y)$。

​ 数论卷积：$[x^n](f(x)*g(x))=\sum_{d|n}f(d)g(\frac{n}{d})$。积性函数卷积仍为积性。鸽

​ 当 $C$ 为完全积性函数时有 $(A\cdot C)*(B\cdot C)=(A*B)\cdot C$。

​ Mobius 反演：设 $f,g$ 为积性函数，有

$f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$

​ 整除式：

$f(n)=\sum_{d\leq n}t(d)g(\lfloor\frac{n}{d}\rfloor)\Leftrightarrow g(n)=\sum_{d\leq n}\mu(d)t(d)f(\lfloor\frac{n}{d}\rfloor)$

​ 原理：$\mu * 1=\epsilon$。

​ 杜教筛：现欲求 $Sf(n)=\sum_{i=1}^n f(i)$。找到合适积性函数 $g(n)$ 使得 $S(f*g),Sg$ 均易求。

$S(f*g)(n)=\sum_{i=1}^n\sum_{j|i}g(j)f(\frac{i}{j})\\ =\sum_{j=1}^ng(j)\sum_{i=1}^{\lfloor\frac{n}{j}\rfloor}f(i)\\ =\sum_{j=1}^n g(j)Sf(\lfloor\frac{n}{j}\rfloor)$

​ 发现可分块求解。具体地，把 $j=1$ 情况拎出来发现其即欲求 $Sf(n)$，求出等式其他所有部分即可。复杂度 $O(n^\frac{2}{3})$。

​ 常见等式（$\epsilon(n)=[n=1],id_k(n)=n^k,\sigma_k(n)=\sum_{d|n}d^k$）：

$\mu*1=\epsilon\\ \phi*1=id_1$

​ 一个变换：记 $(f\times g)(n)=\sum_i^n f(i)g(\lfloor\frac{n}{i}\rfloor)$，

$f\times(g\times h)=h\times(f\times g)$

​ Min-25 / 洲阁筛：

​ PN 筛：

​ Bell 级数：

​ Dirchlet 生成函数：

多项式 A

​ Lagrange 插值：$n+1$ 个点值 $\{(x_i,y_i)\}$ 可确定唯一 $n$ 次多项式

$f(x)=\sum_iy_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$

​ 连续点值线性插值：若给定的点形如 $\{(i,y_i)\}(0\leq i\leq n)$，则有

$f(x)=\sum_i y_i\prod_{j\ne i}\frac{x-j}{i-j} \\=\sum_i y_i\prod_{0\leq j<i}\frac{x-j}{i-j}\prod_{i\leq j\leq n}\frac{x-j}{i-j} \\=x^{\underline{n+1}}\sum_i\frac{y_i}{i!(n-i)!(-1)^{n-i}(x-i)}$

​ 重心 Lagrange 插值：适用于动态加点：鸽

​ 快速 Fourier 变换 FFT：计算实数域下的多项式卷积。思路是转化为单位根点值序列 $DFT$。对于

$f(x)=\sum a_i x^i$

奇偶分拆，设

$G(x)=\sum a_{2i}x^i,H(x)=\sum a_{2i+1}x^i$

有

$DFT(f(\omega_n^k))=DFT(G(\omega_{n/2}^k))+\omega_n^k*DFT(H(\omega_{n/2}^k))\\ DFT(f(\omega_n^{k+n/2}))=DFT(G(\omega_{n/2}^k))-\omega_n^k*DFT(H(\omega_{n/2}^k))$

其中 $\omega_n^k$ 为 $n$ 次单位根，即 $x^n=1$ 在复数域的解。蝴蝶变换：右右或与左减。实质是循环卷积，即，长度溢出后会卷回来。

​ 快速数论变换 NTT：模意义下用原根代替单位根。特别地，对于模数 $998244353$，一个原根为 $3$。

​ 快速 Walsh 变换 FWT：$O(n\log n)$ 计算与、或、异或卷积，$O(n\log^2 n)$ 子集卷积。定义 $FWT(f(x))$ 为 $f(x)$ 的某种变换满足 $f(x)*g(x)=FWT(f(x))·FWT(g(x)) $，即可类似 FFT 运算。

​ 下定义 $Po(i)$ 为 $i$ 的二进制表示中 $1$ 的个数。

$f(x)=\sum_{i=0}^{n-1}a_ix^i\quad f_0(x)=\sum_{i=0}^{n/2-1}a_ix^i\quad f_1(x)=\sum_{n/2}^{n-1}a_ix^i \\$

$\operatorname{OR}:FWT(f(x))=\sum_i(\sum_{i|j=j}a_j)x^i=(FWT(f_0(x)),FWT(f_0(x))+FWT(f_1(x))) \\$

$\operatorname{AND}:FWT(f(x))=\sum_i(\sum_{i|j=i}a_j)x^i=(FWT(f_0(x))+FWT(f_1(x)),FWT(f_0(x)))\\$

$\operatorname{XOR}:FWT(f(x))=\sum_i(\sum_{\operatorname{Po}(i\&j)\%2=0}a_j-\sum_{\operatorname{Po}(i\&j)\%2=1}a_j)x^i\\ =(FWT(f_0(x))+FWT(f_1(x)),FWT(f_0(x))-FWT(f_1(x)))\\$

​ 逆变换类似。

​ 也可看做二位高维 max 卷积 / min 卷积 / 加法循环卷积，分别对应的变换为高维前缀后缀和和高维 FFT。

​ 若以集合幂级数的形式看待 FWT，三个变换又可看做：

$\operatorname{OR}:FWT(f(x))=\sum_i(\sum_{j\subseteq i}a_j)x^i\\ \operatorname{AND}:FWT(f(x))=\sum_i(\sum_{i\subseteq j}a_j)x^i\\ \operatorname{XOR}:FWT(f(x))=\sum_i(\sum_{j}(-1)^{|i\cap j|}a_j) x^i\\$

​ 子集卷积：

$a_i=\sum_{j\&k=0,j|k=i}b_jc_k=\sum_{\operatorname{Po}(j)+\operatorname{Po}(k)=\operatorname{Po}(i),j|k=i}b_jc_k$

于是对每一组 $\operatorname{Po}(i)$ 相同的 $i$ 开一个多项式然后两两或卷积，即，对占位幂级数的暴力卷积。

​ 子集 exp：前一半递归后与后一半卷积。

​ 分治子集卷积（半在线）：将已知多项式转化为占位幂级数后从 $\operatorname{Po}$ 小的向大的转移（直接在待求多项式和已知多项式的占位幂级数上转移）后还原待求多项式即可。可以看做元素有序的子集 exp。

​ 子集卷积逆：鸽

$\sum_{i\le n}i^2 2^i=O(n^2 2^n)$

​ 分治 FFT：半在线卷积：考虑给定初值的序列 $\{f_i\}$ 满足

$f_n=\sum_{i\le n} f_ig_{n-i}$

​ 运用 CDQ 分治，先计算左半边，把左半边的 $\{f_i\}$ 和整个 $\{g_i\}$ 卷积得到左边对右边的贡献再计算右边。复杂度 $O(n\log^2n)$。

​ 全在线卷积：鸽

​ 任意模数 NTT：三模数 NTT：分别计算出原卷积在 $469762049,998244353,1004535809$ （原根均为 $3$）模下的结果并用 exCRT / exGCD 计算。

​ 多项式求逆：定义多项式乘法逆元 $f^{-1}(x)*f(x)\equiv 1\mod x^n$。

​ 倍增求解，设$f_0(x)$为$f(x)$的前$n/2$项并且已求出其在模$x^{n/2}$意义下的逆元$f_0^{-1}(x)$，有

$f^{-1}(x)=f_0^{-1}(x)(2-f(x)f_0^{-1}(x))\mod x^n$

​ 多项式牛顿迭代：给定$g(x)$，$g(f(x))\equiv 0\mod x^n$，有

$f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\mod x^n$

​ 多项式开方：定义$(f^{1/2}(x))^2\equiv 1\mod x^n$，有

$f^{1/2}(x)=\frac{1}{2}(f_0^{1/2}(x)-f(x)f_0^{-1/2}(x))\mod x^n$

​ 多项式 Ln：定义$ln(1-f(x))=-\sum_{i=1}\frac{1}{i}{f^i(x)}$，有

$ln(f(x))=\int\frac{f'(x)}{f(x)}dx$

$f(x)$常数项需为$1$。

​ 多项式 Exp：定义 $e^{f(x)}=\sum_{i=0}\frac{1}{i!}f^i(x)$，有

$e^{f(x)}=e^{f_0(x)}(1-ln(e^{f_0(x)})+f(x))$

$f(x)$ 常数项需为 $0$。

​ （注：$e^{f_0(x)}$ 为 $f_0(x)$ 在模 $x^{n/2}$ 意义下的结果）

​ Exp 的组合意义：有标号对象无序集合。

​ Euler 变换：定义 $Eu\ f(x)=\prod(\frac{1}{1-x^i})^{[x^i]f(x)}$。通过取 Ln 再求 Exp 计算。组合意义：无标号对象无序集合。

​ 多项式快速幂：对于常数项为 $1$ 的 $f(x)$，先求 Ln 后直接乘法最后 Exp 即可。

​ 否则设其最低次项次数为 $a_ix^i$，先整体除以 $a_i x^i$ 使常数项为 $1$，最后再乘上 $a_i^k x^{ik}$ 即可。也可倍增快速幂在$O(n\log n\log k)$ 解决。

​ 多项式除法 / 取模：定义多项式的除法为

$f(x) \div g(x)=Q(x)\cdots\cdots R(x)\\ f(x)\equiv R(x) \mod{g(x)},(f(x)-R(x))g^{-1}(x)=Q(x)$

设 $f^R(x)$ 为 $f(x)$ 翻转系数后的结果，有

$f^R(x)\equiv Q^R(x)g^R(x)\mod{x^{n-m+1}}$

多项式求逆求解。

​ 多项式多点求值 / 快速插值：对于 $f(x)$ 在 $x_0\dots x_n$ 处的多点求值，令：

$G(x)_{L,R}=\prod_{i=L}^R(x-x_i)$

有

$f(x_i)= (f\mod G_{0,mid})(x_i)\ \ \ (i\le mid)\\ f(x_i)= (f\mod G_{mid+1,n})(x_i)\ \ \ (i> mid)\\$

对于由 $(x_0,y_0),(x_1,y_1),\dots (x_n,y_n)$ 插值的多项式 $f(x)$ ，有

​ 多项式复合函数 / 复合逆：鸽

多项式 B

​ 常系数齐次线性递推：设有递推式 $f_n=\sum_{i=0}^{m-1} f_{n-i-1}a_i$，计算

$x^n \mod{(x^m-\sum_{i=0}^{m-1} x_{m-i-1}a_i)}$

的结果与初值序列 $\{b_i\}$ 点积即得。

​ 常系数非齐次线性递推：鸽

​ 整式递推：鸽

​ 下降幂/一般幂/上升幂多项式：定义

x^\overline{n}=\prod_{i=0}^{n-1}(x+i)\qquad x^\underline{n}=\prod_{i=0}^{n-1}(x-i)

有如下关系

x^\overline{n}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\qquad x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^\underline{i}\\ x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^\overline{i}\qquad x^\underline{n}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i

多项式前缀和：鸽

​ 单位根反演：对于复数域上 $n$ 次单位根 $\omega_n$，有

$[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}$

​ Chirp-Z Transform / Bluestein：可看做广义 FFT。可用以计算

$\forall p,f(c^p)=\sum a_ic^{ip}$

方法是转化为减法卷积式后用普通 FFT 求解。

$f(c^p)=\sum a_ic^{ip}\\=\sum a_ic^{\binom{i+p}{2}-\binom{i}{2}-\binom{p}{2}}\\ =\frac{1}{c^{\binom{p}{2}}}\sum \frac{a_i}{c^{\binom{i}{2}}}c^{\binom{i+p}{2}}$

​ **高维（多元）多项式运算：**各维独立计算。鸽

​ 生成函数方法：鸽鸽鸽鸽

组合数学

​ 排列组合：$n$ 个元素的全排列个数 $A_n=n!$。从 $n$ 个元素中选 $m$ 个，方案数

$\dbinom{n}{m}=\frac{n!}{m!(n-m)!}$

组合数还有性质

$\dbinom{n}{m}=\dbinom{n-1}{m-1}+\dbinom{n-1}{m}\\ \sum_{i=0}^n\dbinom{i}{k}=\dbinom{n+1}{k+1}\\ \dbinom{a}{b}\dbinom{b}{c}=\dbinom{a}{c}\dbinom{a-c}{b-c}\\ \sum_{i=0}^n\dbinom{n}{i}^2=\dbinom{2n}{n}\\ \sum_{i=0}^n\dbinom{n-i}{i}=F_{n+1}(斐波那契）\\ \sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k} \\ \cdots$

​ 组合数比大小：取 $\ln$。

​ 二项式定理：

$(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^ib^{n-i}$

​ 二项式反演：对于 $f(x),g(x)$，有

$f(n)=\sum_{i=0}^n\dbinom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n\dbinom{n}{i}(-1)^{n-i}f(i)$

​ Catalan 数：$C_n$ 表示多边形三角剖分方案数；有根二叉树方案数；出栈方案数。

有递推式

$C_n=\sum_{i=1}^nH_{n-i}H_{i-1}(n\geq 2)$

有通解

$C_n=\frac{\dbinom{2n}{n}}{n+1}=\dbinom{2n}{n}-\dbinom{2n}{n-1}(n\geq 2)$

​ Strling 数：第一类 Strling 数 $\begin{bmatrix}n\\m\end{bmatrix}$ 表示把 $n$ 个不同元素组成 $m$ 个圆排列的方案数；第二类 Strling 数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示把 $n$ 个有标号元素划分为 $m$ 个无标号集合的方案数。

有

$\begin{bmatrix}n\\m\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}+\begin{bmatrix}n-1\\m-1\end{bmatrix}\\ \begin{Bmatrix}n\\m\end{Bmatrix}=m\begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$

对于第二类 Strling 数，有通项

$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^i\dbinom{m}{i}(m-i)^n$

​ 幂转 Strling 数：下降幂。幂转组合数：考虑 $n$ 个有标号球放入 $m$ 个有标号盒子，枚举空盒数量变成 Strling + 组合数。

​ 上升幂下降幂反转：$x^{\overline n}=(-1)^n(-x)^{\underline{n}}$，反之亦然。

​ 反转公式：

$[n=m]=\sum_{m\le i\le n}(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\m\end{bmatrix}=\sum_{m\le i\le n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\m\end{Bmatrix}$

​ Strling 反演：

$f(n)=\sum_i^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum_i^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}f(i)$

​ Eulerian 数：$\lang\begin{matrix}n\\m\end{matrix}\rang$表示 $n$ 个元素的排列有 $m$ 个升高的方案数。

有

$\lang\begin{matrix}n\\m\end{matrix}\rang=(m+1)\lang\begin{matrix}n-1\\m\end{matrix}\rang+(n-m)\lang\begin{matrix}n-1\\m-1\end{matrix}\rang$

和组合数间有关系（Worpitsky 恒等式）：

$x^n=\sum_k\lang\begin{matrix}n\\k\end{matrix}\rang\dbinom{x+k}{n}$

有通项

$\lang\begin{matrix}n\\m\end{matrix}\rang=\sum_{k=0}^m (-1)^k (m+1-k)^n \binom{n+1}{k}$

​ Bell 数：$B_n$ 表示 $n$ 个有标号元素划分成若干无标号集合的方案数。

$B_n=\sum_{i}^n \begin{Bmatrix}n\\i\end{Bmatrix}\\ B_n=\sum_{i}^{n-1}\dbinom{n}{i}B_i$

​ Bernoulli 数：等幂求和各次项系数模式。

$S_m(n)=\sum_{i=1}^{n-1}i^m=\frac{1}{m+1}\sum_{k=0}^m\dbinom{m+1}{k}n^{m+1-k}b_k$

​ 容斥原理：

$|\bigcup_i S_i|=\sum_i|S_i|-\sum_i\sum_j|S_i\cap S_j|+\cdots+(-1)^{m-1}\sum_{\{p_i\}}|\bigcap_i S_{p_i}|+\cdots+(-1)^{n-1}|\bigcap_i S_i|$

即：加上一次的，减去两次的，...

$|\bigcap_i S_i|=|U|-|\bigcup_i \overline{S_i}|$

即：集合的交等于全集减补集的并。

​ Min-Max 容斥：

$\max(U)=\sum_{S\subseteq U}(-1)^{|S|-1}\min(S) \\ \min(U)=\sum_{S\subseteq U}(-1)^{|S|-1}\max(S)$

​ K Min-Max：

$kth\max(U)=\sum_{S\subseteq U}(-1)^{|S|-k}\dbinom{|S|-1}{k-1}\min(S)$

​ 容斥反演：对于集合函数 $F,G$，

$F(S)=\sum_{T\subseteq S}G(T)\Leftrightarrow G(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}F(T)$

​ 也为集合幂级数子集变换的逆变换。

​ Burnside 引理：对于一置换群 $G$，将其作用在集合 $A$ 上得到的等价类个数为所有置换不动点个数的平均数。

$|A/G|=\frac{1}{|G|}\sum_{g\in G}|A^g|\\ A^g=\{x|x\in A,g(x)=x\}$

​ Polya 定理：Burnside 引理在染色问题上的推论。

$|A/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)}$

$c(g)$ 表示置换 $g$ 能拆分成的不相交的循环置换的数量。

线性代数

​ 高斯消元：$O(n^3)$ 求解一次方程组。从上到下从左往右将矩阵化为上三角形态，然后自下而上递推即可。

​ Gauss-Jordan 消元：消元时，不仅往下消，也往上消，最后把主对角线全化为 $1$。

​ 矩阵：

$(A*B)_{i,j}=\sum_k A_{i,k}B_{k,j}$

单位阵 $I$ 为仅有主对角线为 $1$ 的方阵。

​ 有结合律，一般无交换律。为保持矩阵性质，重定义的乘法需满足结合律。

​ 转置运算：行列交换。$(AB)^T=B^TA^T$。

​ 迹：主对角线元素和。

​ 秩：极大线性无关行数。

​ 谱：$Av=\lambda v$，则 $\lambda$ 为 $A$ 的一个特征值，$v$ 是对应特征向量。全体特征值为谱。

​ 行列式：仅对于方阵。等于所有排列元素之积乘 $-1$ 的逆序对个数次方的和。计算法则：

• 交换行，行列式值取反；
• 单行数乘，行列式值同时乘；
• 单行加法分解，行列式对应行加法分解，得到两个行列式值后相加；
• 转置，行列式值不变；
• 一行乘一个数加到另一行，行列式值不变；
• 不满秩的矩阵行列式值为 $0$；
• 对行 / 列展开：行列式等于某一行的所有元素乘其代数余子式的行列式值之和。

​ 可使用高斯消元，化为上三角后求主对角线乘积即可。

​ 矩阵求逆：在右边拼同阶单位阵成为 $\{A|I\}$，做 Gauss-Jordan 消元后即为 $\{I|A^{-1}\}$。

​ 逆矩阵的行列式为矩阵行列式的倒数。

​ 线性规划：寻找线性不等式组约束下线性函数的极值问题。一般型：所有变量 $\ge 0$，所有约束所有变量在左侧常量在右侧，所有约束符号相同，最小化 / 最大化目标线性函数值。

​ 单纯形：鸽

​ 对偶原理：对偶线性规划最优解相等。$\min\Leftrightarrow\max$；变量和式子互换；小于大于互换；系数与约束数互换；所有变量依然 $\ge 0$。

抽象代数

​ 群：

​ 代数运算与系统：

博弈论

​ Nim 游戏：多堆石子，每次从一堆中取任意个，无法行动者输。后手获胜条件为所有堆异或和为 $0$。

​ 带限制 Nim：每次只能在一堆中取小于等于 $m$ 个。获胜条件为所有堆$\mod{m+1}\ $后异或和为 $0$。

​ 阶梯 Nim/树形 Nim：形如从下面取再放到上面的形式。获胜条件为奇数层/偶数层异或和为 $0$。

​ Anti-Nim：获胜条件反转。定义奇异局势为异或和为 $0$ 的局势，定义充裕堆为 $\ge 2$ 的堆。定义状态：S0/S1/S2 为非奇异局势下充裕堆为 0/1/2 的状态，T0/2 为奇异局势下充裕堆为 0/2 的状态。转移：S0 必败；T0 必胜：转移到 S0；S1 必胜：转移到 S0；T2 转移到 S1 和 S2，若 T2 转到 S2 则 S2 可转回 T2，于是 S2 必胜，T2 必败。

​ Multi-Nim：Nim 加入规则：取一堆后，可将取的那一堆分裂成多堆。获胜条件同 Nim。

​ SG 函数：记 $mex(S)$ 表示最小的在 $S$ 中未出现的非负整数。对于公平组合博弈的某一状态，其 $SG$ 值定义为其所有后继状态的 $mex$。SG 定理：一个状态后手必胜当且仅当其 $SG$ 值为 $0$；对于多个有向图游戏组成的游戏（双方可在任意一个游戏中移动），后手必胜当且仅当所有的 $SG$ 值异或为 $0$。

​ Whythoff 游戏：二人两堆石子，操作：任意的一堆中取走任意多的石子；两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。结论：差值乘 $\phi$ 取下整为较小数则后手胜。

​ Beatty 定理：设 $a,b\in R_+\backslash Z_+$，$\frac{1}{a}+\frac{1}{b}=1$，则 $P=\{\lfloor na\rfloor\},Q=\{\lfloor nb\rfloor\}(n\in Z_+)$ 构成 $Z_+$ 划分。

​ Fibonacci 博弈：二人一堆石子。先手最少取一个，至多无上限，但不能取完，之后每次取的不能超过上一次取的的二倍且至少为一，取走最后一个石子的人获胜。结论： $n$ 为 Fibonacci 数则后手胜。

​ Shannon 游戏：对于一无向图 $G$，负玩家（先手）和正玩家轮流执行操作：负玩家每次删掉一条未固定的边删去，正玩家每次选择一条未删去的边固定，操作结束后若 $G$ 联通则正玩家胜。正玩家胜利条件： $G$ 中有两棵边独立生成树（边不交的生成树）。

​ 二分图博弈：给一张二分图和初始在某一位置棋子，双方轮流移动至之前未移动过的位置，无法操作者输。先手必胜条件：初始棋子在所有最大匹配方案上。先手获胜策略：不断走匹配。后手获胜策略：找一个不在的方案，先手移动一步后必定位于一个匹配点，并且走不到非匹配点。

​ Nash 博弈（策略式博弈）：对于静态（各方同时行动），一次（一次决策），完全信息，非合作的博弈，游戏各方均采取最优反应（对手不变时自己的决策最优）时达到纯策略 Nash 均衡。游戏各方以一定概率选择自己的每一个决策达到最优反应时，每个纯策略的收益期望相等，达到混合策略的 Nash 均衡。用线性规划求解。

​ Bayes-Nash 均衡：对于动态博弈（各方不同时行动），后手对于先手的决策使用 Bayes 定理计算后验概率并调整自己的决策。

​ Surreals：超实数域 $No$ 是最大的有序域。一个超实数 $x=\{x^L|x^R\}$ 由两个数集（左集 $x^L$，右集 $x^R$）构成，满足左集中不存在数 $\ge$ 右集中的某数。

x\ge y \Leftrightarrow \nexists x^R \le y \and\nexists x \le y^L\\ x+y=\{x^L+y,x+y^L|x^R+y,x+y^R\}\\ -x=\{-x^R|-x^L\}\\ x=y\Leftrightarrow x\le y\and x\ge y

有 $0=\{|\},a=\{a-1|\}(a\ge 0),b=\{|b+1\}(b\le 0)$ 。对于一个数$x$，若存在至少一个数 $z$ 满足
$x^L < z < x^R$ ，则其中最简单的数即为 $x$ 的值。这里的“最简单”可以理解为在二叉树中所在层数最低的。

​ 定义一个博弈 $x=\{x^L|x^R\}$ 由两个数集（左集 $x^L$，右集 $x^R$）构成，可能不满足左集中不存在数 $\ge$ 右集中的某数。博弈的大小比较与 Surreals 一致。若 x\nleq y \and x\ngeq y ，则称 $x||y$。

​ 博弈的组合意义：左方行动后达到的状态集合和右方行动后达到的状态集合。对于博弈 $G$ 有：

$G>0\Leftrightarrow G左方必胜\\ G<0\Leftrightarrow G右方必胜\\ G=0\Leftrightarrow G后手必胜\\ G\ ||\ 0\Leftrightarrow G先手必胜$

​ 博弈技巧：策略交换

5.图论 Gra

图

​ 邻接表 / 邻接矩阵 / 链式前向星表储存。

​ 图的遍历：BFS 保证源点到所有点经过的边数最小，即，无权图的 $O(n+m)$ 最短路。

​ 无向图的 DFS 树只存在树边和返祖边。有向图的 DFS 树存在树边返祖边前向边横插边，除树边外的其它边都由 DFN 序大的指向 DFN 序小的点。

​ DFS 后，所有非树边代表一个环，环套环生成环（异或边），可生成图中所有环。

拓扑排序

​ 先找所有入度为 $0$ 的点加入队列后删除之，逐步递推出图的拓扑序。未入队列的点即成环。

​ DAG 排序后可压扁成链状物。

​ 支配树：支配问题：对于有向图中每个点 $u$ 找到所有的点 $v$ 满足去掉 $v$ 后从 $1$ 无法到达 $u$。称点 $p$ 为 $u$ 的直系支配点当且仅当 $u$ 的其他所有支配点都支配 $p$，记为 $p=idom[u]$。所有点与其直系支配点之间的连边构成树，称为支配树。

​ 称点 $q$ 为 $u$ 的半支配点，当且仅当存在一条从 $q$ 到 $u$ 的路径使得其上掐头去尾后所有点都大于 $u$（DFN 序大于 $u$），记其中最小的 $q$ 为 $q=semi[u]$。有性质：$idom[u]$ 是 $semi[u]$ 的祖先，$semi[u]$ 是 $u$ 的真祖先；所有点与其 $idom$ 在 DFS 树上构成的所有链要么包含要么不交。

​ 求解：对于点 $X$ 和 $Y$ 有边 $Y\rightarrow X$，则若 $Y<X$，则 $Y$ 是 $X$ 的一个半支配点，否则对于 $Y$ 的祖先链上所有 $Z>X$，$semi[Z]$ 都是 $X$ 的半支配点；对于点 $X$ 找到在 DFS 树上链 $(semi[x],x]$ 中 $semi$ 最小的点 $Z$，若 $semi[X]=semi[Z]$，则 $idom[X]=semi[X]$，否则 $idom[X]=idom[Z]$。按 DFN 序从大到小计算并使用带权并查集维护。

生成树

​ Prim算法通过每次找最小的点构造生成树并用堆优化方式实现。Kruskal 算法把边排序后从小往大加直到加到 $n-1$ 条合法边为止，可不显式建图。复杂度 $O(m\log m)$。

​ 性质：环切性（新加一条边时替换环上最大边）；拟阵。

​ Kruskal 重构树：做 Kruskal 时对于每次可行的加边操作，把边视作新点并把两端点当前所属集合作为其儿子，形成一棵二叉树。

​ 次小生成树：对于每条非树边尝试用它代替环上最大树边。严格次小：保存环上最大边和次大边。

​ 最小树形图：对于每个点选定其最小出边，若出现环则缩环并重设边权重复上述流程。Tarjan 算法可在 $O(m+n\log n)$ 时间内完成该操作。任意源最小树形图通过加入超级源实现。全源最小树形图：鸽。

​ 生成树计数：适用于可能有重边但无自环的图。使用 Matrix-Tree 定理计数。图的生成树个数等于其 Laplace 矩阵的任一个 $n-1$ 阶主子式（去掉同行同列的矩阵的行列式）的值。Laplace 矩阵：度数矩阵（第 $i$ 行第 $i$ 列为点 $i$ 度数）－邻接矩阵。有向图内向树：度数矩阵为出度；外向树：度数矩阵为入度。

​ 最小 Steiner 树：联通图上给定点集的最小树。做法是状压，设 $f[S][x]$ 表示当前联通集合 $S$，当前节点在 $x$ 的最小树。转移：合并两个集合（$f[S\cup T][x]\Leftarrow f[T][x]+f[S][x]$）；转移根（$f[S][x]\Leftarrow f[S][y]+w[x][y]$）。

​ Boruvka：维护一些连通块，每轮对于每个连通块找到该连通块内部所有点向外部所有点最短边，按序加入并合并连通块。执行 $O(\log n)$ 轮，复杂度 $O(n\log n)$。适用：边太多而有规律时。

最短路

​ Dijkstra 算法每次找最小点构造最短路，无法处理负权。SPFA 通过不断入队节点序列找到最短路，复杂度 $O(nm)$。SPFA 判负环：有一个点入队超过 $n$ 次。Floyd 算法通过枚举中继点实现全源最短路，$O(n^3)$。Johnson 算法全源最短路（势能法）：增加虚拟源点向每个点连 $0$ 权边，做 SPFA 求出源点到所有点的最短路 $h_i$，对于 $<u\rightarrow v,w>$，重设其边权为 $w+h_u-h_v$，再做 $n$ 次 Dijkstra。

​ K 短路：鸽

​ 最短路建图形如 A 比 B 多 $d$（或以内）。

​ 最短路计数：记录每个点的最短路 $s_i$。若发现一条边 $<u\rightarrow v,w>$ 满足$s_u+w=s_v$则转移之。

​ 差分约束：形如 $\{x_i-x_j\leq c_k\}$ 的一组不等式。把$x$看做节点，对于一约束关系转化为边$$<j\rightarrow i,c_k>$$。若找到负环则无解。否则最短路即为解。

​ 同余最短路：解 $a_1x_1+\cdots+a_mx_m\le n$ 的解组数。方法是分析其中一个 $a_i x_i$（一般取最小的），设 $s_d$ 是最小的模 $a_i$ 等于 $d$ 的能表示出来的数。有性质：$s_d+a_j\ge s_{(d+a_j)\bmod a_i}$，连边做最短路即可。

​ 最短路树：是 DAG。删点最短路：把最短路树按拓扑序拍扁后找到该点位置，然后划分成前后两段，预处理前后缀可求解。

连通性

​ 割点/桥：Tarjan 算法：对图进行 DFS，记录每个点的 $dfn_x$ 和 $low_x$ 表示 $min(dfn_i,dfn_j)$，$i$ 为 $x$ 子树中的点，$j$ 为 $i$ 不经过树边一步能到达的点，即，$low_x$ 表示不经过父亲能到达的最小时间戳。对点 $x$，割点判断条件为$low_v\geq dfn_x$，割边为 $low_v> dfn_x$（$v$ 是 $x$ 的儿子）。

​ 点 / 边双联通分量：点双联通分量包含其外围的第一圈割点。边双连通分量不包含任何割边；所有点双覆盖所有点和边还多覆盖割点，所有边双的并不覆盖割边。点双退栈退到 $x$ 加入但不退，边双不加入也不退。

​ 强联通分量：Tarjan 中若发现 $dfn_x=low_x$，则栈中 $x$ 后面的点构成 SCC，顺次弹出。最后栈中剩余节点也构成 SCC。Tarjan 求得的 SCC 编号反拓扑序。

​ 动态图连通性：离线运用线段树分治 + 并查集或 LCT 维护删除最晚生成树。在线：通过赋边权的方式维护 $\log$ 个不同子图和其对应生成树，删边 / 加边时对每个子图操作。

​ 动态图强联通 / 双联通：求出两点在同一强 / 双连通分量中的最小时刻。运用整体二分 / CDQ 分治，设当前时间区间为 $[l,r]$，把前一半时间的边离线 Tarjan，如果一个边完全在一个分量内部，就丢到左边，否则丢到右边；然后递归左边，然后把前一半的点缩到一起，递归右边。

​ 联通图计数 / 联通子图计数：

LGV 引理

​ DAG 中存在 $n$ 个 < 起点 $a_i$，终点 $b_i$ > 对，每个起点要走到对应的终点，要求各路径点不相交。总方案数为

$\begin{vmatrix} s(a_1,b_1) & s(a_1,b_2) &\cdots & s(a_1,b_n)\\ s(a_2,b_1) & s(a_2,b_2) &\cdots & s(a_2,b_n)\\ \vdots&\vdots&\ddots&\vdots\\ s(a_n,b_1) & s(a_n,b_2) &\cdots & s(a_n,b_n)\\ \end{vmatrix}$

三元环计数：给边定向，从度数大的向度数小的。然后枚举第一个点，给所有它一步到达的点打标记（第二个点），再在所有它一步到达的点的邻点中找标记（第三个点）。三元环数 $O(m\sqrt{n})$。

欧拉路

​ 无向图存在欧拉路径仅当其有 $0/2$ 个奇度数点。无向图存在欧拉回路仅当其为偶图。有向图存在欧拉路径且不存在欧拉回路仅当其有一点入度比出度大 $1$，有一点入度比出度小 $1$。有向图存在欧拉回路仅当其所有点入度出度相等。

​ 找到一条欧拉路径：Fluery 避桥：每次跑一边 Tarjan，优先走不是桥的边。

​ Hierholzer 套圈（找回路）：DFS 并标记每一条边，如果走到一个没有未标记出边的点就加入回路前端。复杂度 $O(m+n)$。

​ BEST 定理：运用 Matrix-Tree 定理计数。欧拉图的欧拉回路条数等于其以任意一个点为根的内向生成树个数乘以每个点的出度减 1 的阶乘之积。欧拉图以任意一个点为根的内向生成树个数均相等。欧拉图的内向生成树与一组欧拉回路对应。注意判自环和 $(-1)!$。

​ 欧拉图计数：

树

​ 树上差分：鸽

​ 最近公共祖先：倍增法：记录每个点$i$向上跳 $2^j$ 能跳到的位置。求 $LCA(x,y)$ 时，先把 $x,y$ 跳到同深度，再把它们不断尝试跳到最大的跳不到一起的地方。ST 表套 Euler 序：两点的 $LCA$ 必是欧拉序上其位置中深度最小的点。预处理后 $O(1)$ 查询。

​ 树的直径：树上的最长路径。直径的中点到最远点最近。可一遍 DFS 求解。直径可并性：两树用一条边相连，新树直径端点必为原来四端点之一。线段树套 Euler 序：转化为 $max_{a\leq c\leq b}dpt_a+dpt_b-2*dpt_c$ 后线段树维护。

​ 树的重心：该点作为根时，最大的子树最小。可一遍 DFS 求解。重心可并性：两树合并，重心必在原来的重心连线上。

​ Prufer 序列：构造：每次取编号最小的度数为 $1$ 的点，删除之并记下与之相邻的点，直到剩下最后两个点。每个点的出现次数为其度数 $-1$。$n$ 点有标号无根树与长为 $n-2$，每个数都在 $[1,n]$ 的序列一一对应。

​ 树同构：无根：有根：有根考虑儿子顺序：

​ Cayley 定理：$n$ 点有标号无根树有 $n^{n-2}$ 种。

​ 重链剖分：对每个点记其 $size$ 最大的儿子为重儿子并连重边，其余为轻边。从根到任意点的轻边条数 $O(\log n)$，转化为 $dfn$ 序后子树为连续段，树链为 $O(\log n)$ 条连续段。

​ 长链剖分：对每个点记其 $maxdpt$ 最大的儿子为长儿子并连长边，其余为短边。从根到任一点短边 $O(\sqrt{n})$。所有长链长度和 $O(n)$。优化 DP：对于二维状态 $f_{i,j}$（$i$当前点$j$深度），直接继承其长儿子并把其余儿子暴力合并，复杂度 $O(n)$。

​ 树上 k 级祖先：有性质：任意一个点的 $k$ 级祖先所在长链的链长一定大于等于 $k$。倍增预处理 $2^i$ 级祖先，对于长为 $len$ 的长链，记录链顶向上 $len$ 级的点。跳祖先时先跳一个最大的 $2^p\leq k$，发现 $k$ 级祖先必在当前位置所在长链不远处（链顶上下 $len$ 范围内），于是可 $O(1)$ 求解。

​ 点分治：处理复杂度形如 $O(\sum size_i)$，与树的形态基本无关的问题。每次分治地处理一树上连通块，找到该连通块重心，计算和重心相关的答案，再删除重心递归计算每个子树。

​ 点分树：鸽

​ 边分治 & 边分树：每次从一条边分治。因为可能不平衡，需先进行三度化转二叉树。特点：分治问题只有两部分，易于合并。边分树合并：

​ 链上点分治 / 点分树，又称中点分治 / 猫树。

​ 虚树：鸽

特殊的图

​ 仙人掌：任意两简单环不相交的连通图。

​ 圆方树：对仙人掌中的每个环建一个虚点连向所有点并保存环上信息。

​ 广义圆方树：对每一个点双联通分量建虚点连向所有分量中的点，构成一棵树。

​ 串并联图：

​ 2-SAT：对于若干 $0/1$ 变量 $x_i$ 和形如 $x_i\ne x_j$ 的关系求合法解。把每个变量拆成两个点，对于每个关系正反连边。无解仅当同一个变量的两点在同一连通块内。输出方案：按拓扑序确定每一个变量的取值。具体地，考察 $!x$ 的拓扑序是否在 $x$ 之前，若是则取 $x=1$（因为此时等价于：如果不选 $x$，就选 $x$，所以选 $x$）。

​ 多边形图：形态为凸多边形剖分。对偶图为树形结构。若为三角剖分，则对偶图为二叉树。

​ 平面图：

​ 欧拉公式：$|V|-|E|+|F|=|C|+1$，$|C|$ 是连通块数。

​ 判定：$m\le 3n-6$。Kuratowski 定理：图是平面图当且仅当不存在同胚于 $K_5$ 或 $K_{3,3}$ 的子图。Tarjan法。

​ 对偶：每条边变成两条单向边，这样每条单向边属于唯一平面。对每个点的所有边极角排序。从一条边 $<s,t>$ 开始，每次找到 $<t,s>$ 的上一条边 DFS，直至成环。遍历所有边即可。

​ 弦图：

​ 补图、线图、对偶图：补图是边的有无反转；线图是边化点，边相交则点连边；对偶图是面点转化。

图匹配

​ 二分图最大匹配：匈牙利算法：对于每一个点找增广路（交错路）增广（翻转交错路上所有边），$O(nm)$。最大流算法：源点向左部点连边，右部点向汇点连边，中间全为 $1$ 边作最大流，$O(m\sqrt{n})$。

​ 二分图最大权匹配：先补点补边成完全二分图最大权完美匹配。费用流算法：跑费用流。

​ KM 算法：注意到最大权匹配 = 最小顶标和。设 $X_i,Y_i$ 分别为左右两部点的顶标，初始化为 $X_i=inf,Y_i=0$。对于右侧一个 $vis=0$ 的点 $p$，记其 $slack=min_i(X_i+Y_p-w_{i,p})$，记其 $pr$ 为使 $slack$ 取最小的 $i$。寻找 $n$ 轮增广路：

• 右侧所有点的 $vis:=0$，$slack:=inf$；
• 对于左侧每一个未匹配点，用它的权值更新右侧点的 $slack$，$vis$ 不变，对于所有已匹配点，$vis:=0$.
• 找到右侧 $slack$ 最小的点 $p$，对左侧所有 $vis=1$ 的点更改顶标减去 $slack_p$，对右侧所有 $vis=1$ 的点加上 $slack_p$，相应更改 $slack$（对 $vis=0$ 的点 $slack-=slack_p$）。找到 $slack$ 最小点，看其是否被匹配，如果是，则用其匹配点的顶标更新右侧点的 $slack$ 重复上述步骤，否则找到一条增广路。
• 沿路增广。交替跳右侧点的 $pr$ 和左侧点的匹配位置。

原理：

• 不显式维护相等子图；
• 每次增广动态构建交错树直至找到一条增广路；
• 交错树的所有 左->右边都是当时调整顶标后 相等子图中 出现的 新边；
• 右->左边都是原匹配边；
• 构造：用 左侧当前交错树中所有点 更新 右侧所有非交错树中的点，找到 slack 最小的右侧点；
• 用该点 nd 调整顶标：对于 当前交错树上 所有左侧点顶标减小 nd，右侧点增加 nd；
• 重设 slack：交错树上点 slack 不变（原因：左右抵消），否则减小 nd。
• 判断该点有无匹配点，若无，找到增广路。否则将该点匹配点加入交错树。

复杂度 $O(n^3)$。

​ 一般图最大匹配：调整法：随机取未匹配点看是否有未匹配邻点，若是则匹配，否则随便取邻点强行匹配。

​ 带花树算法：

​ 一般图最大权匹配：带权带花树：

​ 稳定匹配：

网络流

​ 最大流：Dinic 算法：用最短路径（不带权）将图分层每次按层序找增广路，复杂度 $O(n^2m)$，快。当前弧优化：记录每个点当前第一条可以增广的出边。

​ 预流推进 HLPP：

​ 最小费用最大流：用最短路（费用为权，SPFA）将图分层找增广路，复杂度 $O(nmf)$（伪多项式），有凸性。Primal-Dual 原始对偶算法：类似 Johnson 算法，先求出源点到每个点的最短路 $h_i$，将每个边权重置为 $h_i+c_{i,j}-h_j$ ，再进行 Dijkstra 算法，再增广，增广后设源点到每个点的距离为 $d_i'$，重置 $h_i+=d_i'$。 Capacity Scaling 费用流：先加一条从终点到起点的边化为无源汇最小费用流，有性质：负环即增广路。注意到对于一张图，若每条边容量乘 $2$，则最小费用流所有边流量乘 $2$。费用拆位计算（类似快速幂）化为全局乘 2 和边加 1，暴力 +1 后判断是否产生负环并增广之，复杂度 $O(n^2m\log f)/O(nm^2\log f)$，取决于用 Dijkstra 实现还是 SPFA 实现。

​ 最小费用流：EK 增广至单次费用为正。

​ 负费用最大流：EK 增广至总费用为负。

​ 动态流 / 退流：加边直接跑；删边 $<u,v>$ 跑 $maxflow(u\rightarrow S),maxflow(T\rightarrow v)$ 后清空该边和反边流量；修改费用先删边再加边。

​ 上下界流：设下界为 $b$ 上界为 $c$。无源汇上下界可行流：先给每条边流量预先加上 $b$，再连 $c-b$ 边，为使流量平衡，新建源点汇点分别向溢出 / 不足的点连边，看是否满流。有源汇上下界可行流：汇向源连大边。有源汇最大流：先找可行流，再在残量网络上跑原源汇最大流。最小流：先不连汇到原的边跑超源到超汇的最大流，再连上，再在残量网络上求超源到超汇的最大流，新加的边上的流量即是最小流。最小费用可行流：类似可行流，改为求超源到超汇的费用流。

​ 最小割树：一张图中本质不同的最小割只有 $O(n)$ 种。建树时递归，每次从当前节点集合中选出两个点 $x,y$，求最小割并连树边，然后求出残量网络中所有 $x$ 能到达的点和不能到达的点递归。每次都在整张图上跑。图中任意两点的最小割为其在树上路径的边权最小值。

​ 建图：二分图匹配：源点连左汇点连右。最小路径点覆盖：把每个点拆成两个点，对每条有向边 $<u,v>$ 连 $<u,v+n>$，最小路径覆盖的路径数等于 $n-$ 二分图最大匹配。可重最小路径点覆盖：传递闭包转化。集合划分模型：超源超汇向所有点连边跑最小割。修车模型：发现第 $i$ 个车主在第 $j$ 个师傅的倒数第 $k$ 位置修车总共产生贡献 $k*t_{i,j}$。棋盘：行列拆分或黑白染色。切糕模型（距离限制模型）：向距离外点连边跑最小割。最大权闭合子图：超源连所有权值为正的点超汇连权值为负的点（类似集合划分），最小割为所有不选的正点和所有选了的负点，输出方案：所有超源能到达的点。最大密度子图：二分答案，注意到关系 “ 如果一条边选了那么它的两个点必须被选 ”，转化为最大权闭合子图求解。

若干等式

​ 二分图最大匹配 = 最小点覆盖 = $n-$ 最大独立集。图的最大团 = 补图最大独立集。DAG 最小路径点覆盖 = $n-$ 拆点二分图最大匹配。最大流 = 最小割，最小割可行边 $<x,y>$ 满足 $x\nrightarrow y$（不存在 $x$ 到 $y$ 的路径），必须边 $<x,y>$ 满足 $S\rightarrow x\&\& y\rightarrow T$。平面图最小割等于对偶图最短路。点数 - 边数 = 联通块数（树）。Hall 定理：二分图存在完备匹配（左侧全匹配）的充要条件：左侧任意 $k$ 个点至少与右侧 $k$ 个点相邻。

6.计算几何 Geo

向量

凸包 & 半平面交

扫描线 & 面积差分

若干定理

​ Picks：

7.二分，分治，分块 Div

二分

​ 二分查找：在有序数组中二分，看当前数与要查找数的关系。$O(\log n)$。

​ 二分答案：二分当前答案看是否可行。需满足答案单调性。以 $O(\log n)$ 的复杂度把最优化问题转化为可行性问题。

​ 分数规划：二分答案后化式子，一般转化为 $\geq 0$ 或 $\leq 0$ 的可行解问题。解决最优比率生成树 / 最小环问题。

​ 三分 / 斜率二分：三分法求单峰函数极值（Fibonacci 优选）；斜率二分求凸函数极值。

​ 线段树二分：二分答案时直接用线段树的整段二分。

​ 权值二分：求解凸函数上某一点点值。二分斜率使截距最小 / 最大使直线与凸包相切，计算此时点值并二分。

​ 整体二分：对所有询问同时二分答案，对当前答案以某种手段处理问题分成小于当前和大于当前的两种询问左右分治。

分治

​ 线段树分治：对每个操作在线段树上化为 $O(\log n)$ 个影响区间，每个询问从线段树顶切下找到$O(\log n)$个影响它的区间并统计贡献。

​ CDQ 分治：适用于贡献独立。离线。先计算左半段，再统计左边对右边的贡献，再计算右半段。

​ 根号分治：对每个询问如果小于 $B$ 暴力否则维护整体信息（根号平衡）。

​ 数据分治：用两种暴力过小数据和大数据。

​ 中点分治：计算所有过中点的询问并左右分治。同点分治。

​ 二进制分组：适用于贡献独立。在线。在当前状态维护 $O(\log)$ 个组，每个组维护 $2^i$ 个单个贡献。新加入贡献时合并已有组。（二进制计数器加 1，手动进位）

​ 广义二进制分组（重构分组）：维护一个单调栈保存当前所有组。新加入贡献时判断最后一个组的大小是否大于前一个组的 $\alpha$ 倍，若是则合并退栈。

​ 二进制拆分：唯一拆分不重覆盖。或用 $\log$ 次拆分全覆盖。

分块

​ 普通分块：序列分 $B$ 块，区间操作时小块暴力，整块打标记。

​ 块状链表：支持 $O(\sqrt{n})$ 定位插入定位删除。方法是把序列分块再把这些块串起来，插入时跳链表暴力插入删除同理。若块长大于 $2\sqrt{n}$ 需分裂，相邻块过小需合并。

​ 树分块：在树上标记一些关键点把树划分成若干联通块。保证：每个点向上 / 下走不超过 $B$ 步走到关键点或每个点距最近的关键点不超过 $B$。

​ 操作分块：

莫队

​ 普通莫队：$O(n\sqrt Q)$。先把序列分成 $\frac{n}{\sqrt Q}$ 块，双关键字排序：左端点所在块、右端点位置。每次维护左指针右指针每次移动一步。奇偶分开排序降 2 倍常数。适用：离线全询问，单次移动端点可快速解决。

​ 带修莫队：即为三关键字莫队。把序列以 $n^{\frac{2}{3}}$ 分块，排序：第一关键字所在块、第二关键字所在块、第三关键字。复杂度：$O(n^\frac{5}{3})$。

​ 回滚莫队：找到每组左端点块组按右端点排序。每次单调移动右端点、撤回原先左端点移动再移动左端点。支持只能增加 / 删除的情况，需要可撤销化。

​ 莫队二次离线：因为询问是离线的，在回答询问时把莫队指针的每一次移动对询问的贡献记录下来，最后离线整体回答。

​ 树上莫队：可将树做成括号序后作普通莫队。可树分块后排序：首先若左端点 DFN 大于右端点，交换之，之后按左端点所属块、右端点 DFN 为关键字排序。

8.杂项

IO 优化

inline int qread(){int nans=0;char c=getchar();while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9')nans=nans*10+c-'0',c=getchar();return nans;}

​ fread：只用于文件输入。先定义长为 $2^{23}$ 的字符数组 buf 和指针 p1,p2。

#define getchar ((p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2))?EOF:*p1++)

统计

​ 高精度：乘法 FFT。除法从上往下滚动模拟长除法。

​ 离散化：排序 + 去重 + lower_bound。

​ $O(1)$ long long 乘法：

ll mul(ll x,ll y,ll np){return (x*y-(ll)((long double)x/np*y)*np+np)%np;}

搜索

​ IDA*：估价函数；启发式搜索。

​ 舞蹈链：在双向循环十字链表上快速删除行 / 列。$O(玄学)$ 解决精确覆盖问题。

随机化

​ 爬山算法：在当前点找最优解爬。多次随机选取起点。

​ 模拟退火：当前点有一定概率爬到劣解，概率与爬山时长成负相关。多次随机选取起点。

​ 多源退火：当前记录一个点集合，每次随机从集合中拓展记录下一次迭代的当前最优解集合。

​ 调整法：保证当前答案不变劣。通过某种调整的手法从当前答案变化为价值不低于它的解。

​ Born-Kerbosch 最大团：

STL

​ bitset：时空复杂度 $O(\frac{1}{w})$ 的 bool 数组。函数：count 返回 1 的个数，flip 全体翻转，_Find_first 返回第一个 1，_Find_next 返回下一个 1。

启发式算法

​ 启发式合并：小的往大的上面合并。

​ 启发式分裂：分裂时找到较小的暴力更新。方法是：分裂时同时遍历左边右边每次一个顶一个，一边扩展不下去时该边即为小的那一边。

势能分析

​ 势能类线段树：

​ 单调操作：

9.

高维偏序

​ 在线加一维。二维用树状数组，三维 CDQ 或树套树，四维 CDQ 套 CDQ 或树套树套树或 K-D tree。更高维用 bitset：对每一维记矩阵 $A_{i,j}$ 表示在这一位 $i$ 是否小于 $j$，最后全与起来即可。

​ 【多关键字最优化型】：枚举一个剩下的顺次做

​ 【区间数颜色】

​ 【补集转化】

​ 【时间轴反转】

​ 【树上差分 / DFN】可处理链加单点查询

​ 【树上链交 / 链并】

​ 【二进制分组】

​ 【做菜类】

​ 【接水果类】

​ 【树上最优排列】：堆+合并儿子

​ 【模拟费用流】

​ 【堆式贪心】

​ 【质因数分治】

​ 【矩阵加速】

杨表

​ 一个高度不升的表格称作杨图。在表格中填数，满足每列严格递增每行单调不减叫做半标准杨表；每行严格递增，每个数恰好出现一次形成排列叫做标准杨表。

​ 杨表插入 $x_0$（对行插入）：在第一行找到严格大于该数的第一个数 $x_1$，把 $x_0$ 填进去换出来 $x_1$，把 $x_1$ 再按该方法填入下一行，直到在一行 $K$ 找不到严格大于 $x_{K-1}$ 的数，此时把 $x_{K-1}$ 填入该行最后一列。记 $x_0$ 的插入位置为该行最后一列（可用一个附属杨表记录）。杨表删除（对行删除，只能删除一行最后一列）：不断找到上一行最大的比当前数小的数并置换之，直到到达第一行并退出。

​ 对应关系：一个排列与一对标准杨表对应（一个是插入杨表，一个是记录位置的杨表）。一个矩阵对应于一个序列对（若 $A_{i,j}=k$ 则 $<i,j>$ 出现 $k$ 次）对应于一对半标准杨表。序列对（第一关键字排序）生成杨表对：将第二关键字依次插入，位置杨表记录第一关键字；设序列对 $X=\{<u_i,v_i>\}$ 按 $u_i$ 排序后生成的杨表对为 $<P_X,Q_X>$，按 $v_i$ 排序后生成 $<P_X^{-1},Q_X^{-1}>$ ，则有 $<P_X,Q_X>=<Q_X^{-1},P_X^{-1}>$。转置矩阵的杨表对等于原杨表反过来。对称矩阵与一个半标准杨表对应。对称矩阵的迹（主对角线元素和）等于杨表长为奇数的列数。

​ 一个每行每列恰有一个 $1$ 的矩阵对应于一个排列。满足如上条件的对称矩阵称为对合矩阵，对应排列称为对合排列，对之计数可得对合数，大小为 $n$ 的标准杨表个数即为对合数，一个排列的不动点数量与对应杨表长为奇数的列数相等。排列的反转的杨表为原杨表的转置。**杨表第一行长度为 $LIS$ 长度，前 $k$ 行长度为 $k-LDS$（最长的 $LIS\leq k$ 的子序列）长度。**前 $k$ 列同理。

​ 钩子公式：对形状为 $\lambda$（一个整数拆分）的标准杨表个数计数，答案为

$f_{\lambda}=\frac{n!}{\prod_{i,j}h_{\lambda}(i,j)}$

其中 $h_{\lambda}(i,j)$ 为满足 p=i,q\geq j\or p\geq i,q=j 的格子 $(p,q)$ 个数。数在 $[1,n]$ 的半标准杨表个数为

$g_{\lambda}=\prod_{i,j}\frac{n-i+j}{h_{\lambda}(i,j)}$

决策单调性

​ 证明：打表找规律

​ 定义单调矩阵为每行最小值位置单调不降的矩阵。完全单调矩阵为所有子矩阵都是单调矩阵的矩阵。

​ 称矩阵 $A$ 上的四边形不等式为 $\forall i<j,k<l,A_{i,k}+A_{j,l}\le A_{i,l}+A_{j,k}$。即，小小 + 大大 < 小大 + 大小。若 $A$ 满足四边形不等式，则 $A,A^T$ 完全单调。

​ 判定：$A_{i,j}+A_{i+1,j+1}\le A_{i,j+1}+A_{i+1,j}$ 则 $A$ 满足四边形不等式。

​ 求每行最小值位置：需保证矩阵元素可快速得到。

​ 离线单 $\log$ 分治法：设 $f(l,r,L,R)$ 为当前欲求 $l-r$ 中的答案，已确定范围在 $[L,R]$ 中。暴力求 $mid$ 对应答案 $aid$，然后变成 $f(l,mid-1,L,aid),f(mid+1,r,aid,R)$。离线决策单调性问题：$f_{i,j}=\min_{k<j}(f_{i-1,k}+w_{k,j})$。

​ 在线单 $\log$ 二分栈法：对于每一列 $i$，必然存在区间 $[l_i,r_i]$ 使得 $[l_i,r_i]$ 中行最小值所在列都是 $i$，并且 $[l_i,r_i]$ 随 $i$ 单增。考虑顺次加入每一列，则当前列的区间必然为一个后缀区间。维护一个栈表示已加入的列。如果加入新列 $i$ 发现栈顶 $j$ 出现 $A_{l_j,j}\ge A_{l_j,i}$ 则 $j$ 整个区间都没了，直接退栈，否则在 $j$ 的区间中二分 $i$ 的左端点加入之。在线决策单调性问题：$f_{j}=\min_{k<j}(f_k+w_{k,j})$。

​ 离线（几乎）线性：SMAWK 法：如果列比行多则一定会出现一些列不是任何行的答案，找到并删除之。取所有奇数行递归计算答案，偶数行在奇数行的空隙中暴力。

​ 在线（几乎）线性：Wilber 法。

​ 区间 DP ：若 $f_{i,j}=\min(f_{l,i}+f_{i,r})+w_{l,r}$ 且 $w$ 满足四边形不等式，则 $f$ 满足四边形不等式。若 $f$ 满足四边形不等式，则 $f_{i,j}$ 的最优决策点在 $f_{i-1,j}$ 和 $f_{i,j+1}$ 决策点之间（即，区间左右各扩展 1 得到的区间），通过枚举区间长度优化。

​ 区间划分 DP：给定 $K$，$f_{n}=\min(\sum_{i_1,\cdots,i_K}w_{i_j,i_{j+1}})$。即，把 $[1,n]$ 划分为 $K$ 个子区间，求这些子区间 $w$ 之和的最小值，其中 $w$ 满足四边形不等式。性质：若固定 $n$，对所有 $K$ 答案下凸。可再加一维，变成 $f_{m,n}=min(f_{m-1,i}+w_{i,n})$。可 wqs 二分后转化为求每行最小值位置。性质：对固定 $K$，对 $y>x$，$f_y$ 字典序最小的一组转移点的每一个转移点都比 $f_x$ 对应字典序最小转移点靠后，即，决策点整体单调。推广：对任意区间若把其左端点右端点同时右移则转移点依然整体单调。

​ 蒙日阵上 TSP：最优回路一定是最优双调回路：满足 $1<i_1<i_2<\cdots<n>\cdots>j_2>j_1>1$ 的哈密顿回路。双调回路用 DP 计算（$dp_{i,j}$ 为 $i<\cdots<n>\cdots>j$ 最优值，需保证 $\min(i,j)\sim n$ 中的点都出现过），DP 中有多个后继的状态只有 $O(n^2)$ 个。提取状态作转移发现变成在线决策单调性问题。

整数拆分

​ 记用不超过 $m$ 的整数无序拆分 $n$ 的方案数为 $p(n,m)$。

​ 枚举最大值个数，有 $p(n,m)=p(n-1,m-1)+(n-m,m)$。

​ Ferres 棋盘：用不超过 $m$ 的整数拆分方案数等于用不超过 $m$ 个数拆分 $n$。理解：棋盘的转置。上面的转移式的另一种理解：末尾插 $1$ 或全体加 $1$。

​ 背包与 Euler 变换：有

$p(n,m)=[x^n]\frac{1}{\prod_{i=1}^m(1-x^i)}$

​ 五边形数与 Euler 函数：设

$\phi(x)=\prod_{i\ge 1}(1-x^i)$

​ 意义为把 $n$ 拆成偶数的方案减去把 $n$ 拆成奇数的方案。

​ 有

$\phi(x)=\sum_{k=-\infin}^\infin (-1)^k x^{\frac{k(3k-1)}{2}}$

​ 于是有

$p(n)=\sum_i(-1)^i(p(n-\frac{i(3i-1)}{2})+p(n-\frac{i(3i+1)}{2}))$

格路计数

只能往上或往右走。

​ 自由路：长度一定为 $n+m$。方案数：$\dbinom{n+m}n$。

​ Dyck 路：设 $n,m$ 互质。从 $(0,0)$ 走到 $(n,m)$，不经过 $y=\frac{m}n x$ 下方的方案数为 $\frac{1}{n+m}\dbinom{n+m}{n}$。

​ 原因：一条格路的最小循环节必为 $n+m$，而在一条格路的所有循环移位中恰有一条合法，这一条是把原格路在离直线下方最远的点拆成两半并右左拼接组成。

​ 1-Dyck 路 & 折线法：走到 $(n,m)$ 中途不碰到 $y=x+a(a< 0)$ 的方案数为 $\dbinom{n+m}{n}-\dbinom{n+a}{m-a}$。

​ 考虑每一条碰到的直线，把第一个碰撞点前的部分沿直线翻折即得。

​ $t$ -Dyck 路：从 $(0,0)$ 走到 $(n,m)$，不经过 $y=tx$ 下方的方案数为 $\frac{m-tn+1}{n+1}\dbinom{n+m}{n}$。

​ $k$ 峰自由路 & $k$ 峰 Dyck 路：$k$ 峰自由路方案数为 $\dbinom{n}{k}\dbinom{m}{k}$。原因：把每一条自由路对应到一个峰点序列上，而每一个峰点序列也恰能对应一条自由路。峰点序列要求横坐标两两不同纵坐标两两不同。

​ $k$ 峰 Dyck 路：方案数 $\frac{1}{k}\dbinom{n-1}{k-1}\dbinom{m-1}{k-1}$.

​ 双限制格路：走到 $(n,m)$ 中途不碰到 $y=x+a,y=x+b$ 方案数 $f(n,m,a,b)$。方法是求碰到 $y=x+a$ 方案数和不碰到 $y=x+a$ 碰到 $y=x+b$ 方案数，后一种情况 $g(n,m,b,a)$ 按 $y=x+b$ 作对称后可以递归。

$鸽$

​ 不相交格路：到 $(n,m)$ 的不相交自由路对数为 $\frac{1}{n+1}\dbinom{n+m+1}{n}\dbinom{n+m}{n}$。

​ 到 $(n,m)$ 的不相交的 $k$ 条 Dyck 路，总方案数为

$\det(C_{n-i-j})_{i,j=1}^k= \begin{vmatrix} C_{n-2}& C_{n-3}& \cdots &C_{n-k-1}\\ C_{n-3}& C_{n-k}& \cdots &C_{n-k-2}\\ \vdots& \vdots&\ddots &\vdots& \\ C_{n-k-1}& C_{n-k-2}& \cdots &C_{n-2k}\\ \end{vmatrix}$

​ 其它路径计数：每次 $(+1,+1)$ 或 $(+1,-1)$ 的格路，旋转。

​ 每次 $x+=k$ 或 $y+=1$ 的格路，整体平移。

拟阵

​ 【循环节】

​ 【数据结构优化建图】

​ 【树上dsu】

​ 【树的节点数比边数多1】/ 平面图欧拉公式。

​ 【平方的组合意义】

​ 【定和非上升序列计数】：转移是末尾插入 $1$ 或整体 $+1$。

​ 【Moore投票】

​ 【Huffman树】

​ 【分段打表】

​ 【打表】

​ 【迭代法】

​ 【行求和等于列求和】

​ 【偏序之和】：容斥降维。

​ 【乘法转加法】：取 $\log/\exp$。

​ 【$(\sum a_i)^k$】$=k\prod\exp a_i$

​ 【可并性 / 可差分性 / 重复敏感性】

10.其他

应试策略

​ 暴力打满

​ 手玩样例；猜结论

​ 注意时间

​ CCF 样例很水所以要对拍；CCF 数据很水所以可以随机化

​ 注意思维题 / 结论题

​ 善用超纲数据结构 / 算法

检查

​ 文件名；***子目录***；输入输出；中间结果；样例；编译选项；时空限制；部分分开关。

NOI Linux

​ 区分大小写。换行符 \n 。

​ 终端：

Ctrl-Alt-T 打开终端
cd 切换目录 .. 父目录 . 当前目录 ./xxx 当前目录下文件
time ./xxx 计时
Ctrl-C 终止当前程序 Ctrl-Z 暴力终止 Ctrl-D 停止输入
top 查看当前进程 top内q 退出 top内k 杀死进程
diff a.out b.out 等价于fc diff -b 忽略空格回车
指定输入 < xxx.in 指定输出 > xxx.out
看目录 ls 看目录带隐藏文件 ls -a 
. 是隐藏文件的前缀
设置：键盘-短快快（第二个字后面+对称+同上） 屏幕-10min无密码 鼠标-最快
终端设置：I型 米黄 无限滚动 设置标题
无限栈：ulimit -s unlimited

g++ & vim & 附件

​ vim 配置：

set nu
set ru
set ts=4
set mouse=a
set autoindent
set ww+=[,],<,>
map <F9> <esc>:w<cr>:! g++ % -o %< -g -Wall <cr>
map <F12> <esc>:! time ./%< <cr>
map <F5> <esc>:! gdb %< <cr>
imap ( ()<left>
imap [ []<left>
imap { {}<left>
inoremap ' ''<left>
inoremap " ""<left>

​ g++ 编译：

-o 指定输出文件
-lm 数学库
-g 开调试
-Wall 全部警告
-std=c++11/14/17 开c++11/14/17版本
-O2/O3/Ofast 开O2/O3/Ofast

提交答案 / 交互 / 通信

鸽

其他

• 做题时尽可能往各种方面思考，不要受限于某一固定思路
• 认真读题不要读错题不要读错题不要读错题
• 合理分配时间，尽量不要在某一个没把握的题上耗费超过两小时
• 心态要放轻松

B.Q.A.C.