rt
写在前面
总结一下板子；顺序没有意义；尽量不会压行（但有时候略微压）；限于本人水平，有概率会错；有些东西的运用要视情况而定，会给出类似伪代码的东西，还有些之间用文字给出流程
关于编译选项，默认是 -O2 -std=c++14 -Wl,--stack=1145141919
关于头文件，默认是万能头 #include <bits/stdc++.h>
关于宏（包括 using ），默认包含以下宏
1 |
|
大部分情况默认数据范围是 int
大部分情况默认 $P$ 为模数， $INF$ 为正无穷
如未特殊说明，那些写在外面的语句就是主函数里的
由于这些板子学习的时间参差不齐，码风可能会有不同，见谅
数据结构
邻接表
1 | struct Edge{ int ne, ver, w; } e[M]; |
使用前要初始化（如何使用： for (int i = h[x]; ~i; i = e[i].ne) ）
并查集
1 | int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); } //路径压缩 |
堆
STL （大根堆）： std::priority_queue<int> q;
手打（小根堆）：
1 | namespace Hp //Heap |
左偏树（小根堆）：
1 | namespace LH //Left Heap |
树状树组
1 | namespace BIT |
注意下标必须从 $1$ 开始，否则会死循环
ST 表
1 | namespace ST |
四毛子
1 | namespace FR //Four Russians |
线段树
1 | namespace LT |
注意空间开 $4$ 倍
莫队
1 | 读入 |
莫队二次离线
1 | namespace TOF //Twice Offline |
分块
额……，略
点分治
1 | int get_si(int x, int fa) |
边分治
注意点数要开 $2$ 倍，边数开 $4$ 倍
1 | int si[N << 1], mxs, rte; |
平衡树
STL1 ： std::set<int> s;
STL2 ：
1 |
|
Splay ：
1 | namespace Splay |
优点是可拓展性强，缺点是慢（被卡的化可以试试多转几下）
FHQ Treap ：
1 | namespace FHQ |
补充一个按大小分裂（但是指针码风）
1 | void split(Node *u, int si, Node *&x, Node *&y) |
优点是好打且较快
SBT ：
1 | namespace SBT |
优点是快
跳表
1 | namespace SL //Skip List |
CDQ 分治
1 | void cdq(int l, int r) |
这个顺序不是严格的，可以先左右都递归了再计算中间
李超线段树
1 | struct Line |
主席树
普通：
1 | namespace CT //Chairman Tree |
带修：
1 | namespace BIT |
K-D Tree
1 | struct Point{ int x[D], w; }; |
笛卡尔树
1 | void build() |
哈夫曼树
二叉：
1 | 建立小根堆q,把所有点放入 |
多叉：
1 | 用权值为0的点补足点数,使(n - 1) % (k - 1) == 0 |
树链剖分
重链剖分：
1 | void dfs1(int x, int father, int depth) //求每个的重儿子 |
长链剖分：
1 | void dfs1(int x, int fa) |
动态树
以 UOJ207 为例（LCT 维护子树异或和）
1 | struct LCT |
补充，如何用 LCT 支持一些奇怪的操作：
维护子树信息和：思路是维护虚子树信息和；
access只要在更换右儿子的同时维护一下即可；而在link的时候， $x$make_root后把 $y$ 要access再splay一下避免 $y$ 有祖先信息需要维护维护边权：思路是每个点定义他的“前一条边”和“后一条边”，前一条边指的即是他在原树中与父亲之间的边（可能不存在)，而后一条边指的是在当前的链剖分下，与他在同一条剖分链上的儿子与他之间的边（可能不存在），然后每个点维护它的维护他的前一条边和后一条边是哪条，注意是维护是哪条边，而不是直接维护边权
考虑这两两个边的修改：在
link的时候， $x$ 的前一条边要修改；在cut的时候，一个点的前一条边设成没有，另一个的后一条边设成没有；在access的时候，我们有更换 $x$ 的右儿子的操作，即改变了当前的链剖分，所以 $x$ 的后一条边理应变成他新的右儿子所在的 splay 里最左边的点的前一条边，而为了找到这一条边，我们还需要维护每个 splay 的第一条边和最后一条边，即最左边的点的前一条边和最右边的点的后一条边，（为什么要维护最后一条边呢，因为在翻转的时候我们要交换这两个值）；然后我们对每个点维护他的 splay 子树所代表的链的边权信息和（注意一个 splay 所代表的链所包含的边只有那些两个端点都在这个 splay 里的边）；那么我们考虑这个信息的合并，如果一个点有左子树，那么他的前一条边的另一个端点一定在左子树里，所以他的链信息和就要加上左子树的链信息和以及他的前一条边的信息，右子树亦然；我们考虑链修改操作，与链信息合并类似，如果他有左儿子，那么更改他的前一条边的权值，右儿子亦然，然后对这个点打标
字符串
KMP
1 | ne[1] = 0; |
下标均从 $1$ 开始
Z函数
1 | Z[1] = s_len; |
下标从 $1$ 开始
Trie
普通：
1 | namespace Trie |
Trie 的根是 $1$ ；注意空间要开够
可持久化：
1 | namespace Trie |
任然是要注意空间
最小表示法
1 | int get_min(char *s) //求串s的最小表示,完成后答案存在s[k...k + len - 1]中 |
注意空间要开两倍
Manacher
1 | int manacher(char *s) |
AC 自动机
1 | namespace AC |
SAM
1 | namespace SAM |
广义 SAM
离线版：
1 | struct Trie |
在线：
1 | struct SAM |
SA
1 | namespace SA |
图论
最近公共祖先
树上倍增法：
1 | void dfs(int x, int fa) |
常数较打，优点是好打且可用于求一个点的 $k$ 级祖先
树剖：
1 | 在前面树剖的基础上加入如下代码: |
优点是常数小
ST 表：
1 | int dep[N << 1], cnt = 0, id_b[N << 1], id[N], lg2[N << 1]; //注意2倍 |
优点当然是 $O(1)$ 查询，缺点是有点难打
也可以用四毛子，但太难打了几乎用不到
单源最短路
Dij ：
1 | void dij(int star) |
spfa（慎用）：
1 | void spfa(int star) |
判负环
1 | bool spfa(int star) //判断是否有能从star到达的负环 |
差分约束
1 | 建图: |
多源最短路
Floyed ：
1 | memset(dis, 0x3f, sizeof dis); |
当然也可以做 $n$ 次单源最短路
最小生成树
Kruskal ：
1 | struct Edge{ int from, to, w; } e[M]; |
Prim ：
1 | memset(dis, 0x3f, sizeof dis); |
Kruskal 重构树
Kruskal 重构树的建树流程为：
- 把所有边排序，记边为 $(x, y, z)$ ，表示 $x \to y$ ，权为 $z$
- 构建 $n$ 个无权点，没有边
- 每次取出一条边 $(x, y, z)$ ：
- 若 $x, y$ 联通（在同一棵树），不管它
- 否则，新建一个节点 $t$ ，记 $x, y$ 所在树的根为 $r_x, r_y$ ，让 $t$ 的左右儿子分别为 $r_x, r_y$ ，并让 $t$ 的点权为 $z$
不难发现 kruskal 重构树有如下性质：
- 它是一棵二叉树（更进一步，它其实就是个二叉堆），树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点
- 除叶节点外，儿子节点对应边一定排序在父亲前面，即从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的
- 对于叶节点 $x, y$ ， $lca(x, y)$ 对应的边就是最小生成树中联通 $x, y$ 的“瓶颈边”（它排序在最后）
树的直径
dp 自然可以，但不好求出具体的路径
两次 bfs/dfs 的流程如下：
- 任选一个点出发，找到离该点最远的节点 $p$
- 从 $p$ 出发，找到离 $p$ 最远的节点 $q$
- $p, q$ 间的路径就是树的一条直径；如要得到具体路径，在进行 $2$ 时记录前驱即可
无向图 Tarjan
判桥：
1 | void tarjan(int x, int in_e) |
边双联通分量：
1 | 在判桥的代码后加入以下代码: |
判割点：
1 | void tarjan(int x) |
点双联通分量：
1 | 在上面求割点的代码的(1), (2)处加入以下两段代码: |
有向图 Tarjan
强连通分量：
1 | void tarjan(int x) |
2-SAT
1 | 建图: |
圆方树
直接对原图进行无向图 Tarjan ，因为原图上每个环都是一个点双，而且在栈中的顺序就是环上点的顺序，如果一个点 $i$ 的出边 $(i, j)$ 满足 $dfn(i) < low(j)$ ，说明 $(i, j)$ 是一条树边，直接加上即可；如果 $dfn(i) = low(j)$ ，那么我们找到了一个环（可能是重边造成的二元环），则从栈中取出点直到取出 $j$ 为止，设这样从栈中取出的点集为 $R$ ，则 $i$ 和 $R$ 构成一个环
对于环，我们新建一个方点，对环上每个点连边即可
1 | void tarjan(int x) |
注意新图的节点数变成两倍
三元环计数
要改造一下边，把无向图变成有向图，总时间为 $O(m \sqrt{m})$ ，这同时也是三元环的个数上界
1 | 读入数据,去掉重边,记录每个点的度(下面假设用PII存的边) |
四元环计数
我们将每个点按度数大小重新编号，度数相同原来编号大的点在前的方法，就可以通过编号直接得到任意两个点的关系
设重新编号后排名为 $rk$ ，枚举四圆环中 $rk$ 最大的点 $x$ ，再枚举 $x$ 的出点 $y$ ，枚举 $y$ 的出点 $z$ （这里直接枚举无向边，注意判断 $rk(x) > rk(y) > rk(z)$ ）， 这里就得到了一个长度为 $2$ 的链了，再枚举一个点 $c$ ，只要 $rk(x) > rk(c)$ 就计入答案的贡献，不管 $rk(c)$ 和 $rk(z)$ 的关系
时间复杂度还是 $O(m \sqrt{m})$ ，注意四元环的个数上界是 $nm\sqrt{m}$ ，可能要 LL
1 | 读入数据,记录每个点的度 |
欧拉回路
1 | void euler() |
二分图
判定：染色法
求最大匹配：
网络流可做，这里介绍匈牙利，时间为 $O(nm)$ ：
1 | bool dfs(int x) |
一般图最大匹配
智慧法（可能被卡）：
1 | std::mt19937 rud(114514); |
带花树：
1 | link同上,get就是并查集 |
Prufer 序列
每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点，重复 $n - 2$ 次后就只剩下两个结点，算法结束，得到的序列可以与原树一一对应
虚树
1 | void ins(int x) |
虚树的空间和撤销是易错点
常见转换
- 原图的最大独立集大小 = 补图的最大团大小
二分图：
- 最大独立集大小 = 总点数 - 最小点覆盖大小
- 最小点覆盖大小 = 最大匹配大小
- 最小边覆盖大小 = 总点数 - 最大匹配大小
MCS
1 | namespace MCS |
Bron-Kerbosch
1 | int n, m; |
DP
背包
注意下面初始化都是 0xcf （最小值）
$01$ ：
1 | memset(f, 0xcf, sizeof f), ans = -INF; |
$01$ 退背包（只能求方案数）：
1 | for (int i = 1; i <= m; ++i) f[i] -= f[i - 1] * x; //禁用贡献为x的物品 |
完全：
1 | memset(f, 0xcf, sizeof f), ans = -INF; |
多重背包二进制拆分（以下给出拆分代码）：
1 | void split(Node x) |
多重背包单调队列优化：
1 | int calc(int i, int u, int k){ return f[u + k * v[i]] - k * w[i]; } |
单调队列优化
1 | int q[N], l = 1, r = 0; |
各操作顺序不是严格
斜率优化
考虑 $j$ 优与 $k$ 的条件，把 dp 方程化成 $\frac{Y(j) - Y(k)}{X(j) - X(k)} \le 无关j,k的值K$ 的形式，然后分情况（以最大值为例）：
$X, K$ 单调：
1 | int q[N], l = 1, r = 0; |
$X$ 不单调， $K$ 单调：
1 | int find(int i, int k) |
$X, K$ 都不单调：
1 | bool cmp(int x, int y){ return X(x) == X(y) ? Y(x) > Y(y) : X(x) < X(y); } |
四边形不等式
式子： $a \le b \le c \le d$ 若 $w(a, d) + w(b, c) \ge w(a, c) + w(b, d)$ 则满足四边形不等式（想象一个四边形，对边和小于对角线和）
分治打法：
设函数 sol(l, r, L, R) 表示“当然正在处理 $d[l \sim r]$ ，最优决策存在于区间 $[L, R]$ ”，函数伪代码如下：
1 | sol(l, r, L, R) |
要求 $val(i, j)$ 不含与 $d[j]$ 有关的项
队列 + 二分打法：
1 | q[h = t = 1] = {0, 1, n}; //把0先入队 |
SOS
子集：
1 | for (int i = 0; i < N; ++i) |
超集：
1 | for (int i = 0; i < N; ++i) |
期望
$$
\begin{aligned}
E(ax + b) = aE(x) + b \\
D(ax + b) = a^2 D(x) \\
D(x) = E(x^2) - E^2(x)
\end{aligned}
$$
网络流
最大流（ Dinic ）：
1 | bool bfs() |
最大流（ HLPP ）：
1 | int hi[N], ex[N], gap[N]; //hi:高度,ex:超额流,gap[i]:高度为i的节点的数量 |
费用流
1 | bool spfa() |
最小割树
把 Dinic 的函数改一下：
1 | void init(int _s, int _t) |
再加上：
1 | namespace GHT //Gomory-Hu Tree |
多项式
拉格朗日插值
一般
1 | void init() |
线性
1 | void init(int n) |
FFT
1 | const int N = 3000000 + 5; //注意N要大于二倍n |
NTT + 全家桶
超长警告
1 | const int P = 998244353, I = 86583718, G = 3; //模数,二次剩余,原根 |
upd 2022/7/23 想改成 std::vector 写发，先放一个 exp 其它后面补
1 | namespace Poly |
MTT
1 |
|
计算几何
浮点数比较
1 | int cmp(DB x, DB y) |
平面最近点对
1 | struct Point |
点间距离
1 | DB dist(Point x, Point y) |
向量
用点表示：
1 | struct Point |
点与线
点到直线距离：
1 | DB dis_z(Point p, Point x, Point y) //p到直线(x->y)的距离 |
点到线段距离：
1 | DB dis_x(Point p, Point x, Point y) |
点在直线上的投影：
1 | DB proj(Point p, Point x, Point y) |
点是否在直线上：
1 | bool is_on(Point p, Point x, Point y) |
线与线
直线交点：
注意点向式表达直线： $p = p_0 + t \vec{v}$
1 | Point jiao(Point p, Point u, Point q, Point v) //点项式 |
判断线段是否相交：
1 | bool is_jiao(Point x_1, Point y_1, Point x_2, Point y_2) |
多边形
按逆时针存储所有点
面积：
1 | DB pgarea(Point p[], int n) //polygon area |
判断点是否在多边形内：
射线法，从该点任意做一条和所有边都不平行的射线，交点个数为偶数，则在多边形外，为奇数，则在多边形内
最小圆覆盖
1 | std::mt19937 rud(114514); |
凸包
1 | DB andrew(Point x[]) |
该函数也叫 convex(int x[], int n)
半平面交
1 | struct Line |
旋转卡壳
1 | DB rot_cal(Point x[], int len) |
数论
快速幂
1 | int qpow(int x, int y) |
光速幂
1 | const int BL = (1 << 16) + 5, B = sqrt(P); |
龟速乘
1 | LL mul(LL x, LL y, LL p) |
线性筛
质数：
1 | for (int i = 2; i <= n; ++i) |
莫比乌斯函数：
1 | mu[1] = 1; // 1特判 |
欧拉函数：
1 | phi[1] = 1; |
其它
1 | pri[1] = low[1] = 1; |
杜教筛
式子：$g(1)S(n) = \sum_{i = 1}^{n} (f * g)(i) - \sum_{d = 2}^n g(d) S(\lfloor \frac{n}{d} \rfloor)$
其中 $S$ 是 $f$ 的前缀和，也就是目标，直接筛复杂度 $O(n^{\frac{3}{4}})$ ，预处理 $n^{\frac{2}{3}}$ 个可以降为 $O(n^{\frac{2}{3}})$
1 |
|
min 25 筛
$$
\begin{aligned}
& g(n, j) = \sum_{i = 2}^n f(i)[i \in primes \vee R(i) > p_j] \\
& g(n, j) =
\begin{cases}
g(n, j - 1) & p_j^2 \ge n \\
g(n, j - 1) - f(p_j) * (g(\frac{n}{p_j}, j - 1) - \sum_{k = 1}^{j - 1} f(p_k)) & otherwise
\end{cases} \\
& S(n, j) = \sum_{i = 2}^{n} F(i) [R(i) \ge p_j] \\
& S(n, j) = g(n, cnt) - \sum_{i = 1}^{j - 1} F(p_i) + \sum_{p_k}^{p_k^2 \le n} \sum_{e}^{p_k^{e + 1} \le n} F(p_k^e) \times S(\frac{n}{p_k^e}, k + 1) + F(p_k^{e + 1})
\end{aligned}
$$
1 | void prev(int n) |
分解因数/质因数
根号暴力即可
数论分块
1 | for (int l = 1, r; l <= n; l = r + 1) |
欧几里得算法
1 | int gcd(int x, int y){ return y ? gcd(y, x % y) : x; } |
拓展版：
1 | int exgcd(int a, int b, int &x, int &y) |
BSGS
1 | int bsgs(int a, int b, int p) |
拓展版：
1 | int exbsgs(int a, int b, int p) |
中国剩余定理
1 | LL crt(int m[], int a[], int n) |
拓展：
1 | LL excrt() |
逆元递推式
1 | inv[1] = 1; |
斐波拉契数列推导
$$
\begin{aligned}
& 设系数r,s使得: \\
& F(n) - r F(n - 1) = s[F(n - 1) - rF(n - 2)] \\
& F(n) = (s + r)F(n - 1) - sr F(n - 2) \\
& 那么有: \\
& r + s = 1, rs = -1 \\
& 再考虑这些式子: \\
& \begin{cases}
F(n) - rF(n - 1) = s [F(n - 1) - rF(n - 2)] \\
F(n - 1) - rF(n - 2) = s [F(n - 2) - rF(n - 3)] \\
…\\
F(3) - F(2) = s [F(2) - r F(1)]
\end{cases} \\
& 联立得: \\
& F(n) - rF(n - 1) = s^{n - 2} [F(2) - F(1)] \\
& 又因为: s = 1 - r, F(1) = F(2) = 1 \\
& 有: F(n) = s^{n - 1} + r F(n - 1) \\
& F(n) = s^{n - 1} + r F(n - 1) \\
& F(n) = s^{n - 1} + r s^{n - 2} + r^{2} F(n - 2) \\
& … \\
& F(n) = s^{n - 1} + r s^{n - 2} + r^{2} s^{n - 3} + … + r^{n - 2} s + r^{n - 1} \\
& 等比数列求和得: F(n) = \frac{s^{n - 1} - r^{n - 1}\frac{r}{s}}{1 - \frac{r}{s}} \\
& F(n) = \frac{s^n - r^n}{s - r} \\
& 再由: r + s = 1, rs = -1得: \\
& \begin{cases}
s = \frac{1 + \sqrt{5}}{2} \\
r = \frac{1 - \sqrt{5}}{2}
\end{cases} \\
& 于是 F(n) = \frac{\sqrt{5}}{5}[(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n]
\end{aligned}
$$
威尔逊定理
$(P - 1)! \equiv -1 \pmod P$
欧拉定理
$a^b \equiv a^{b \mod \varphi(P)} \pmod P$
顺便还有欧拉函数的一个运用：
$$
[1 \sim n] 之间与 m 互质的数的个数为 Ans = \frac{n}{m} \varphi(m)
$$
再给出计算式： $\varphi(x) = x \prod \frac{p - 1}{p}, 其中p是x的质因数$
Miller-Rabin 素数测试
1 | const int count = 10; |
调和级数求 $gcd == k$ 的个数
rt，设 $f[k]$ 表示 $gcd(i, j) == k$ 的个数， $g[k]$ 表示 $k \mid gcd(i, j)$ 的个数，那么 $g[k] = f[k] + f[2k] + …$ ，又有 $g[k] = \lfloor \frac{n}{k} \rfloor^2$ ，那么 $f[k] = g[k] - (f[2k] + f[3k] + …)$ ，时间为 $O(n H(n))$ ，由于常数小比莫反略快，而且好打
1 | for (int i = n; i; --i) |
组合计数
组合数计算
$A_n^m = \frac{n!}{(n - m)!}$
$C_n^m = \binom{n}{m} = \frac{A_n^m}{m!} = \frac{n!}{m!(n - m)!}$
特别的，当 $m > n$ 时， $C_n^m = A_n^m = 0$
多重排列： $\binom{n}{n_1, n_2, …, n_k} = \frac{n!}{\prod n_i!}$
错位排列： $f(n) = (n - 1)(f(n - 1) + f(n - 2))$
错位排列2 ： $f(n) = n!(\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - … + (-1)^{n - 1} \frac{1}{n!})$
圆排： $Q_n^r = \frac{A_n^r}{r}$
组合数的一些性质：
$$
\begin{aligned}
& \binom{n}{m} = \binom{n}{n - m} \\
& \binom{n}{k} = \frac{n}{k} \binom{n - 1}{k - 1} \\
& \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m} \\
& \binom{n}{0} + \binom{n}{1} + … + \binom{n}{n} = 2^n \\
& \sum_{0}^n (-1)^i \binom{n}{i} = [n == 0] \
& \sum_{i = 0}^{m} \binom{n}{i} \binom{m}{m - i} = \binom{m + n}{m} (n \ge m)\\
& \sum_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n} \\
& \sum_{i = 0}^n i \binom{n}{i} = n 2^{n - 1} \\
& \sum_{i = 0}^n i^2 \binom{n}{i} = n (n + 1) 2^{n - 2} \\
& \sum_{i = 0}^n \binom{i}{k} = \binom{n + 1}{k + 1} \\
& \binom{n}{t} \binom{t}{k} = \binom{n}{k} = \binom{n - k}{t - k} \\
& \sum_{i = 0}^n \binom{n - i}{i} = F(n + 1) (其中F(n + 1)表示斐波拉契数列)
\end{aligned}
$$
做 $k$ 次前缀异或和，对于最后一个数，第 $i$ 个数被计算次数为 $\binom{n - i + k - 1}{k - 1} = \binom{n - i + k - 1}{n - i}$
Lucas 定理
$\binom{n}{m} \mod P = \binom{\lfloor n / P \rfloor}{\lfloor m / P \rfloor} * \binom{n \mod P}{m \mod P} \mod P$
推论： $\binom{n}{m} \equiv 1 \pmod 2$ 的充要条件是 $m \subseteq n$
卡特兰数
$$
\begin{aligned}
& Cat(n) = \frac{\binom{2n}{n}}{n + 1} \\
& Cat(n) =
\begin{cases}
\sum_{i = 1}^n Cat(i - 1)Cat(n - i) & n \ge 2 \\
1 & n = 0, 1
\end{cases} \\
& Cat(n) = \frac{Cat(n - 1)(4n - 2)}{n + 1} \\
& Cat(n) = \binom{2n}{n} - \binom{2n}{n - 1}
\end{aligned}
$$
莫比乌斯反演
$$
\begin{aligned}
& F(n) = \sum_{d \mid n} f(d) \Rightarrow f(n) = \sum_{d \mid n} \mu(d) F(\frac{n}{d}) \\
& F(n) = \sum_{n \mid d} f(d) \Rightarrow f(n) = \sum_{n \mid d} \mu(\frac{d}{n}) F(d) \\
& \sum_{d \mid n} \mu(d) = [n == 1] \\
& \sum_{d \mid n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n} \\
& d(nm) = \sum_{i \mid n} \sum_{j \mid m} [\gcd(i, j) == 1] (其中d(x)表示x的约数个数)
\end{aligned}
$$
欧拉反演
$$
\begin{aligned}
& \varphi * I = id \\
& \sum_{d \mid n} \mu(d) \frac{n}{d} = \varphi(n) \\
& n = \sum_{d \mid n} \varphi(d) \\
& \sum_{i = 1}^n \gcd(i, n) = \sum_{d \mid n} \frac{n}{d} \varphi(d) \\
\end{aligned}
$$
Dirichlet前缀和
前缀：
1 | for (int i = 1; i <= ct && pri[i] <= n; ++i) |
后缀：
1 | for (int i = 1; i <= ct && pri[i] <= n; ++i) |
逆前缀：
1 | for (int i = ct; i; ++i) |
逆后缀：
1 | for (int i = ct; i; ++i) |
生成函数
普通型 OGF ：
$$
\begin{aligned}
& \prod_{i = 1}^n( \sum_{m \in M_i} x^m) (其中M_i是a_i的出现次数集合) \\
& 常见的有: \\
& \frac{1}{(1 - x)^n} = 1 + nx + \frac{n * (n + 1)}{2!}x^2 + \frac{n * (n + 1) * (n + 2)}{3!} + … \\
& \frac{1}{1 - x} = 1 + x + x^2 + x^3 + …
\end{aligned}
$$
指数型 EGF ：
$$
\begin{aligned}
& \prod_{i = 1}^n( \sum_{m \in M_i} \frac{x^m}{m!}) (其中M_i是a_i的出现次数集合) \\
& 常见的有: \\
& e^x = \sum_{n = 0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + … \\
& \frac{e^x + e{-x}}{2} = \sum_{n = 0}^{\infty} \frac{x^{2n}}{(2n)!} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + … \\
& \frac{e^x - e^{-x}}{2} = \sum_{n = 0}^{\infty} \frac{x^{2n + 1}}{(2n + 1)!} = x + \frac{x^3}{3!} + \frac{x^5}{5!} + …
\end{aligned}
$$
群论
置换群
$n$ 个元素 $1, 2, …, n$ 之间的一个置换 $f = \binom{1, 2, 3, …, n}{a_1, a_2, a_3, …, a_n}$ ，表示“ $1$ 被 $a_1$ 取代， $2$ 被 $a_2$ 取代，依此类推”，其中 $a_1, a_2, …, a_n$是 $1 \sim n$ 的一个排列
Burnside 引理
$$
L = \frac{1}{\mid G \mid} \sum_{j = 1}^s D(a_j)
$$
其中 $L$ 表示本质不同的方案数，$D(a_j)$ 表示在置换 $a_i$ 下不变的元素个数， $\mid G \mid$ 是置换群大小
Polya 定理
记 $c(f)$ 为置换 $f$ 的循环节个数， .$m$ 为颜色总数，有 $D(f) = m^{c(f)}$ ，则有：
$$
L = \frac{1}{\mid G \mid} (\sum_{j = 1}^s m^{c(a_j)})
$$
矩阵
存储
1 | struct Mtx |
LU分解
1 | namespace DLT //Doolittle |
高斯消元
1 | int guass(Mtx &x, int len) //注意传实参 |
矩阵求逆
1 | bool mtxinv(Mtx &x, Mtx &as, int len) |
行列式
1 | int det(Mtx x) |
调用前要保证是正数
Matrix-Tree
1 | int det(int x[][N]) |
$k$ 是度数矩阵减邻接矩阵
其它
快读快输
1 | namespace FIO |
无法读入浮点数；不可以字符串和整型一起读入（但可以一起输出）；注意最后要 flus() 一下；只能文件输入（但可以随意输出），如果要本地输入请 #define gh() getchar()
二分
只会很不优美的写法
1 | int l, r, mid, res; |
三分
1 | int l, r, lm, rm, res, len; |
模拟退火
1 | const DB T0 = 1e4, TE = 1e-4, C = 0.99, SP = 1e3; //这是参数,影响时间和精度 |
取模优化
1 | void adj(int &x){ x += (x >> 31) & P; } |
仅限 $x$ 为负数时可用，当 $x$ 是 LL 时把 $31$ 改成 $63$
Min-Max 容斥
$$
\begin{aligned}
& \max(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - 1} \min(T) \\
& \min(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - 1} \max(T) \\
& kmax(S) = \sum_{T \subseteq S} (-1)^{\mid T \mid - k} \binom{\mid T \mid - 1}{k - 1} \min(T)
\end{aligned}
$$
FWT
1 | namespace FWT |
子集卷积
1 |
|
线性基
1 |
|
sqrt
雷神之锤 3 的神仙开根法：
1 | float Q_rsqrt( float number ) |
不知道有啥用
斐波那契数列循环
求斐波那契数列在模 $p$ 意义下的循环节
循环节长度上界是 $6 \times p$ ，那么每次随机两个 pos 检验该 pos 起始的两位是否出现过（光速幂预处理矩阵），由生日悖论，期望下只要 $O(\sqrt{p})$ 次即可得到一个不一定是最小的循环节，然后枚举其因数验证即可
也可以对矩阵做 bsgs ，设转移矩阵为 $A$ ，那么就是 $A^k = I$ ，由斐波那契定义只 $A$ 一定有逆
- $p = 2, 5$ 手玩
- 否则，若 $p$ 是奇质数：
- 若 $5$ 是模 $p$ 意义下的二次剩余，循环节长度一定是 $p - 1$ 的约数
- 否则，循环节长度一定是 $2p + 2$ 的约数
- 否则， $p$ 是合数，也有结论，但还不如上两个做法
脚本和指令
win：
1 | g++ %1.cpp -o %1.exe -O2 -std=c++14 -Wall -Wextra -Wl,--stack=1145141919 |
linux：
1 | g++ $1.cpp -o $1 -O2 -std=c++14 -Wall -Wshadow -Wextra -Wunreachable-code -Winline -Wpointer-arith |
高精
没写高精除高精
1 |
|