花些时间整理最近做题时写的笔记，还是很有必要的一件事。

之前的内容索引：

一、图论

平面图

首先考虑平面图有什么好性质，它的边数不会很多！实际上（根据论文），大于等于 \(3\) 个点的平面图边数不会超过 \(3n-6\)，也就是说边数和点数是同阶的。

矩阵树定理

所有图允许重边，但不允许自环。

无向图形式

\(L(G) = D(G) - A(G)\)

有向图形式

路径指向根节点 \(rt\) 的树：

\[L_{\mathrm{root}}(G, rt) = D_{\mathrm{out}}(G) - A(G)\]

路径从根节点 \(rt\) 指向叶节点的树：

\[L_{\mathrm{leaf}}(G, rt) = D_{\mathrm{in}}(G) - A(G)\]

注意上面两个都要求去除的是 \(rt\) 的主子式。

BEST 定理

\(G\) 是有向欧拉图，则不同的欧拉回路总数为 \(ec(G)\) 为

\[ ec(G) = \det L_{\mathrm{root}}(G, rt) \prod_{u \in V} (\deg(u) -1)! \]

需要满足的性质：

欧拉图的所有节点有出度 \(=\) 入度；
任意两个节点 \(u, v\) 有 \(L_{\mathrm{root}}(G, u) = L_{\mathrm{root}}(G, v)\)。这个很显然，一个欧拉回路随便拆掉一条边都是一个生成树，所以随便选哪个点做根，根向生成树都应该相等。（我合理推测这个情况还有 \(L_{\mathrm{root}}(G, rt) = L_{\mathrm{leaf}}(G, rt)\)）

后面乘的这个东西相当于，在树上游走，随便选一条边走，这样一个点就贡献 \((\deg(u) -1)!\) 种方案了。

欧拉回路

判断条件：

\(0\) 个或 \(2\) 个奇点
整个图联通

不连通的话，啥都没有了

输出需要倒序输出，不然会有错误。e.g.

从 \(1\) 出发，就会发现还是得逆序……

Q: 是不是只要从一个点出发就好啊

连通分量

Tarjan 求 SCC 和求 BCC 是不一样的，后者并不能走来的边，所以需要记录 pa，前者可以走，所以不需要。

2-SAT

一个妙妙 2-SAT 题目：Radio Station。

有 \(n\) 个电台，有一些电台对需要满足一些基础 2-SAT 条件。此外，每个电台都有一个波长范围 \([l, r]\)，且 \(l, r \leq m\)。你需要找一种方案，使得选出满足条件的电台，且这些电脑波长范围的交不为空（可以假定是 \(f\)，且 \(\forall i,\ f \in [l_i, r_i]\)）。

建立一些 \(f \geq i\) 形式的变量，则 \(f \leq i\) 和 \(f \leq i+1\) 之间的可以添加限制。对于每个电台，也只会和两个新变量之间有限制。这样就在添加线性个变量时解决了问题。

这个题目妙妙点在于，是用 \(f \geq i\) 的形式而非 \(f = i\)。后者虽然也可以解决问题，但是对于新变量之间的限制是 \(\mathcal{O}(m^2)\) 级别的 —— 两两变量之间不能同时都成立。同时，对于一个电台的 \([l, r]\)，也需要和新变量一一添加约束，这样就爆了。

总结：

能使用 2-SAT 的限制实际上是：两个变量不能同时都满足某个条件，而其他情况都是合法的。
对于区间类型的处理，改写成前缀和形式或许会有所帮助。在区间可并性很明显的题目中，这种处理方法很常见（比如区间求和），但是出成 2-SAT 形式就很容易忽略掉这种技巧了。
如果在给一个树构图，且非常清楚每条边的父亲和儿子，那就可以只建一条边，变成一个有向树。

二、数据结构

一个我觉得需要记录的题目：https://codeforces.com/contest/1221/problem/F

平面上有一些有权值的点，求以 \((l, l), (r, r)\) 为顶点的正方形内权值和减去正方形边长的最大值。

注意到一个点 \((x, y)\) 能做贡献的 \((l, r)\)，只有 \(l \leq \min(x, y) \leq \max(x, y) \leq r\) 的区间。比较容易想到固定一个 \(l\)，然后找最优的 \(r\)。对于一个 \(l\) 而言，点 \((x, y)\) 能做贡献的 \(r\) 是一个区间，可以线段树维护。但是随便枚举 \(l\) 的话，就很不好维护这个东西，因为改变了 \(l\)，一些点是否产生贡献的状态就会变化。

化静态为动态，考虑从大到小枚举 \(l\)，这样就相当于动态插入一些点，并且插入的点对后面的影响都是正确的。如果没想到这个东西，实现起来就会有一定困难。

总结：

无序且顺序不影响结果时，排排序可以让处理过程方便：比如 Stone 这个 DP 题目需要记录一下已选序列的最小值，且在无序时需要多一维来记录这个状态。如果改成有序，则就可以和 “枚举到的位置” 这维合并，保证复杂度正确。
需要处理一些互相产生影响的东西时，可以考虑从无到有的方向处理。本题相当于从大到小插入点，保证了大的对小的影响统计是正确的。更通常的做法是化静态为动态，增量式地插入一般能有比较好的性质可以维护。

三、树

树上附近点统计

处理树上到一个点 \(u\) 距离小于等于 \(k\) （比较小）的所有点，可以考虑维护一个点，它子树向下 \(k\) 层的节点信息，则最后答案可以为：

\[ f(v, k) + f(\mathrm{pa}(v), k-1) - f(v, k-2) + f(\mathrm{pa}(\mathrm{pa}(v)), k-2) - f(v, k-3) + \ldots \]

维护子树信息，可以按照欧拉序在进出节点的时候统计差值，就可以轻松维护了。如果一个东西离线做很困难，可以考虑变成动态的：动态更新加点，然后把一个询问拆成两个时间节点的询问。比如 Mokia 和这题。

树分治化 DFS

如果点对间路径统计问题能够挂到两点的 LCA 上，那么一般可以化成树上 DP，然后在 LCA 上统计所有和它相关的路径，感觉比点分治要好写。比如聪聪与可可。

树上路径贡献转移到边

求树上点对总距离，考虑边的贡献 \(=\) 两边点个数乘起来。e.g. CF1060E。即是说，如果答案满足线性性，那么可以分别考虑贡献。

四、数论

皮萨诺周期

计算斐波那契周期性质：http://webspace.ship.edu/msrenault/fibonacci/fibfactory.htm

皮萨诺周期：模 \(p\) 下的周期不超过 \(6n\)，且只有在满足 \(p = 2 \cdot 5^k\) 的形式时才取到等号。

如果要对一个神秘数（比如 \(10^9\)）取模，并且要求 \(F_i\) 前缀和之类和区间有关的东西，可以分别在 \(2^9, 5^9\) 下取模求循环节搞，这样循环节就很小了。

除了 \(2\) 以外，皮萨诺周期都是偶数。原因是转移矩阵 \(\det F = -1\)，而 \(\det F^{\pi (n)} = 1\)，因此 \(\pi (n)\) 必为偶数。

当且仅当 \(p\equiv 1 \pmod 5\) 或 \(p\equiv 4 \pmod 5\) 时，\(5\) 是模 \(p\) 意义下的二次剩余。
当且仅当 \(p\equiv 2 \pmod 5\) 或 \(p\equiv 3 \pmod 5\) 时，\(5\) 是模 \(p\) 意义下的非二次剩余。

下部分参考自求解斐波那契数列模 p 意义下最短循环节 - yicongli。

质数 \(p\) 的皮萨诺周期 \(P(p)\) 满足：

\(P(p) | p-1\)，其中 \(5\) 是模 \(p\) 意义下的二次剩余
\(P(p) | 2p+2\)，其中 \(5\) 是模 \(p\) 意义下的非二次剩余
\(P(p^k) | P(p)\cdot p^{k-1}\)，但是据作者说他并没有找到证明
对于合数来说，给每个质数幂的 \(P(p^k)\) 取 LCM 即可

欧拉降幂

欧拉降幂：需要特殊处理，因为 \(\varphi(n)\) 前后是不一样的，不能先加 \(\varphi(n)\) 再处理。

收敛性

序列的前缀 GCD、OR、AND 具有吸收性，最多只有不超过 \(\mathcal{O}(\log n)\) 种不同的值。

模运算

想要求 \(a\times b^{-1} \pmod p\)，但是 \(b^{-1}\) 可能在模 \(p\) 下不存在，这个时候可以求 \(a \pmod {b\times p}\)，这样左边就可以直接除以 \(b\) 了。简单证明：

\[ a\times b^{-1} \equiv n \pmod p \\ (a\times b^{-1})x + py = n \\ ax + (p\times b)y = n\times b \\ a \equiv n\times b \pmod {p \times b} \\ \]

模 \(2^{64}\)（用 ull）时，应该注意最后再向右移动位数，因为运算过程中并不能保证 \(2\) 的逆存在，除以二可能并不是个整数。由于最后的运算结果一定是个整数，并且一定比答案多了 \(2^n\)，因此最后是可以直接除掉的。

原根

\(n\) 如果有原根，则原根个数：\(\varphi(\varphi(n))\)。不会证明。

光速幂

光速幂：\(a^{bx+c} = (a^x)^b \times a^c\)，预处理 \(a^x\) 和 \(a\) 的 \([0, x)\) 次幂即可。

GCD 的合并

\[ (a, b) = (a, c) = 1 \Leftrightarrow (a, bc) = 1 \]

好像非常显然，但是我会犯蠢。

五、筛法

积性函数

若 \(f, g\) 都是积性函数，则以下函数也是积性函数：

\[ h(x) = f(x^p) \\ h(x) = f^p(x) \\ h(x) = f(x)g(x) \\ h = f \times g \\ \]

狄利克雷卷积满足：

交换律
结合律
分配律
单位元

取 \(g = 1\)，则 \(h(n) = \sum _{d|n} f(d)\) 也是个积性函数。但对一个不是积性函数的 \(a\) 而言，\(b(n) = \sum _{d|n} a(d)\) 可不一定是个积性函数……

\(f\) 是积性函数，则 \(g(n) = nf(n)\) 也是积性函数。

很水的反演过程

\[ \begin{aligned} & \varphi \times 1 = \mathrm{id} \\ \Rightarrow \ & \varphi = \mathrm{id} \times \mu \end{aligned} \]

\[ \begin{aligned} & \mu \times 1 \\ \Rightarrow \ & e = \mu \times \mu \end{aligned} \]

约数个数和

约数个数 \(d(n)\) 和约数和 \(\sigma(n)\) 也是积性函数，且

\[ \sum _{i=1} ^n d(n) = \sum _{i=1}^n \left\lfloor \frac ni \right\rfloor \]

分别考虑每个约数能贡献给谁即可。

\[ d(ij) = \sum _{x|i} \sum _{y|j} [(x, y) = 1] \]

上式显然先决定 \(x\) 的取值，再决定 \(y\) 的取值。对于一个因子 \(p\)，若 \(p^a | i,\ p^b | j\)，且 \(p^{a+b} | ij\)，则

\(p^0 | x\)，则表示 \(y\) 可以任意选 \(p^1, \ldots, p^b\) 等因子，分别对应因数 \(d | p^{a+1}, d | p^{a+2}, \ldots, d | p^{a+b}\)
\(p^1 | x, p^2 | x, \ldots, p^a | x\)，则表示 \(x\) 可以任意选 \(p^1, \ldots, p^a\) 等因子，分别对应因数 \(d | p^{1}, d | p^{2}, \ldots, d | p^{a}\)
\(x = 1, y = 0\)，则表示因数 \(1\)。

综上，因子 \(p^0, p^1, \ldots, p^{a+b}\) 都能被唯一地表示出来且一一对应（双射），因此等式成立。

一些奇怪的式子转化

范围相同的互质对统计

\[ \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = 2\sum _{i=1}^n \varphi(i) - 1 \]

两两互质个数减去 \((1, 1)\) 的情况。也可以写成

\[ \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = \sum _{d=1}^n \mu(d) \left\lfloor \frac nd \right\rfloor ^2 \]

\(\mu\) 的拆解

\[ \mu(ab) = \mu(a) \mu(b) [(a, b) = 1] \]

这个比较显然，因为存在平方因子就是 \(0\) 了。

\(\varphi\) 的拆解

若 \((a, p) = 1\)，则

\[ \varphi(ap^k) = \varphi(a) \cdot \varphi(p) \cdot p^{k-1} \]

这说明对 \(k > 1\) 的质因数 \(p\)，它都可以直接丢出来。换句话说，如果 \(n = \prod p_i^{k_i}\)，令 \(x = \prod p_i,\ y = \prod p_i^{k_i-1}\)，则

\[ \varphi(n) = \varphi(xy) = \varphi(x) \cdot y \]

暂时不知道可以做什么。

min_25 筛

min_25 筛中，分块的方案是这样的（令 \(n = 10\)）：

值	1	2	3	4	5	6	7	8	9	10
向下取整	10	5	3	2	2	1	1	1	1	1
分块点	√	√	√		√					√

即是说，分块点是向下取整的值相同时，能取到的最大值。所以在两个分块点 \((a, b]\) 的部分就是一块，可以直接用 \(f(b) - f(a)\) 当前缀和。

杜教筛

利用杜教筛的技巧可以求一些非积性函数的前缀和。若要求 \(f\) 的前缀和，且满足：

某个函数 \(g\) 的前缀和好求
\(f \times g\) 的前缀和好求

那就有一定可能使用该技巧。一个例子（OEIS：A067824）：

求 \(G(n) = 1 + \sum _{d|n,\ d<n} G(d)\) 的前缀和，其中 \(n \leq 10^9\)。

移项：

\[ 2G(n) - 1 = \sum _{d|n} G(d) \]

两边求前缀和：

\[ \begin{aligned} 2 \sum _{i=1}^n G(i) - n &= \sum _{i=1}^n \sum _{d|i} G(d) \\ &= \sum _{d=1}^n \sum _{d|i} G\left(\frac id \right) \\ &= \sum _{d=1}^n \sum _{i=1}^{\lfloor n/d \rfloor} G(i) \\ &= \sum _{i=1}^n G(i) + \sum _{d=2}^n \sum _{i=1}^{\lfloor n/d \rfloor} G(i) \\ \end{aligned} \]

记 \(S(n) = \sum _{i=1}^n G(i)\)，整理上式得

\[ S(n) = n + \sum _{i=2}^n S \left( \left\lfloor \frac ni \right\rfloor \right) \]

和积性函数的杜教筛区别在于没法线筛，所以预处理范围有限，递归过程可以近似看做是 \(\mathcal{O}(n^{3/4})\) 的。

六、FFT

FWT

FWT_OR:

\[f(A) = (F(A_0),\ F(A_0) + F(A_1))\]

FWT_AND:

\[f(A) = (F(A_0) + F(A_1),\ F(A_1))\]

FWT_XOR:

\[f(A) = (F(A_0) + F(A_1),\ F(A_0) - F(A_1))\]

七、多项式

拉格朗日插值

\[ f(x) = \sum_{i=1}^n y_i \times (\prod_{j\neq i} \dfrac {x - x_j} {x_i - x_j}) \]

如果 \(x_i\) 是 \([1, n]\) 的连续下标，那可以通过预处理阶乘来达到 \(\mathcal{O}(n)\) 的复杂度。

生成函数

形式幂级数 \(\sum_{i = 0} ^ {\infty} a^i x^i = \frac 1 {1 - ax}\) 并不太关注 \(x\) 的取值是否使得式子收敛。给出一些常用生成函数的封闭形式：

完全背包生成函数

\[ \sum _{i=0} ^{\infty} x^{ai} = \frac 1{1-x^a} \]

不知道什么的生成函数

\[ \sum _{i=0} ^{\infty} a^i x^i = \frac 1{1-ax} \]

二项式形式的生成函数

\[ \sum _{i=0} ^{\infty} \binom ni x^i = (1+x)^n \]

广义二项式定理的生成函数

\[ \sum _{i=0} ^{\infty} \binom{n+i-1}{i}x^i = \frac {1}{(1-x)^n} \]

令：扩展组合数为 \(\binom {-n}k = (-1)^k \binom {n+k-1}{k}\)，这个展开就可以验证了。带入二项式定理中可以得到广义二项式定理（见上）。

生成函数与可逆背包

一个非常棒的可逆背包题：2018 沈阳 ICPC 现场 M 题。

\[ \sum _{i=0} ^n x^{ai} = \frac {1-(x^a)^{n+1}}{1-x^a} \]

上面是个负方案的 01 背包，下面是个完全背包，没了。

指数型生成函数

\[ \sum _{i=0} ^{\infty} \frac {x^{2i}}{(2i)!} = \frac {e^x + e^{-x}}2 \]

\[ \sum _{i=0} ^{\infty} \frac {x^{2i+1}}{(2i+1)!} = \frac {e^x - e^{-x}}2 \]

这个性质可以将生成函数化成封闭形式。反过来，也可以将封闭形式转化为级数形式：

\[ e^{ax} = \sum _{i=0} ^{\infty} \frac {a^i x^i}{i!} \]

注意因为是求排列，所以一般最后要乘一个 \(n!\)。

指数型生成函数与集合划分

考虑一些具有性质 \(A\) 的东西的指数型生成函数 \(F(x)\)，现在把 \(A\) 里面的东西当成基本元素，像选物品一样合在一起获得具有 \(B\) 性质的东西（也就是 \(B\) 是几个 \(A\) 属性的东西拼成的），且 \(B\) 的生成函数是 \(G(x)\)，则

\[ G(x) = e^{F(x)} \]

例子

令 \(F(x)\) 为 \(n\) 个点的无向连通图个数，\(G(x)\) 为 \(n\) 个点的任意图数量（且显然 \(G(x) = \sum _{i=0}^{\infty} 2^{i(i-1)/2}x^i\)），因此 \(F(x) = \ln G(x)\)。
令 \(F(x)\) 为 \(n\) 个点的连通 DAG 个数，\(G(x)\) 为不要求连通的 \(n\) 个点的 DAG 个数，显然这也同样满足集合划分要求。

考虑一个小证明：

\(G(x)\) 是 \(F(x)\) 的一个划分，因此对 \(G(x)\) 枚举它由几个 \(F(x)\) 构成：

\[ \begin{aligned} G(x) &= \sum _{i=0} ^{\infty} \frac {F^i(x)}{i!} \\ &= e^{F(x)} \end{aligned} \]

利用该性质可以极大化简某些过程。

八、字符串

询问总串长与不同长度的数量

多次询问字符串，且字符串总和不超过 \(m\)，则不同长度的字符串是 \(\mathcal{O}(\sqrt{m})\) 级别的。证明也很简单，最坏情况是 \(1 + 2 + 3 + \ldots + p\)，这个东西显然长度只有 \(\mathcal{O}(\sqrt{m})\)。因此如果询问某个长度的字符串可以同时处理，那么时间复杂度很可能就有保证。

统计本质不同的子序列

CF1183E 计算本质不同的子序列个数中，如果令 \(f(i, j, c)\) 为第 \(i\) 位以及之前，长度为 \(j\) 且结尾为 \(c\) 的子序列个数，则转移中可能出现的情况是，前面出现一个字符 \(c\)，后面又出现一个字符 \(c\)，后面的字符能够统计前面的字符的所有子序列，这个时候会造成重复。因此最好的办法是，把以 \(c\) 结尾的子序列贡献都移动到最后一次出现的字符上，而不计算更前面的字符，这样就是不重不漏的了。

犯蠢备忘录

变量记得加 static 或者初始化。
min_25 筛和杜教筛，想清楚 \(n\) 代表的是值还是离散化后的值。我默认都是离散化后的值。
如果用 lazy[o] 标志表示区间 Add 次数，则更新时应该乘上 lazy[o]。e.g.

区间加 1，询问区间和
1
s[o] = (R-L+1) * lazy[o]
快速幂 ret 开始为 \(1\) 而不是 \(0\)。
写优先队列的时候注意是 .front() 还是 .back()。
写交互题目记得 cout.flush()！
不要写 memset(dis, 0x3f, sizeof(0x3f)) 这种蠢蠢错误了。
写线性筛的时候注意是 i % p 还是 p % i。

杂项

如果给定了串的长度，说明可能是个空串，要特殊处理。
构造题就往构造题的方向想就好了。
编译器会说话就多说点
- -Wshadow：局部变量覆盖
- -Wconversion：类型转换，但是如果转换过程不改变符号就不会提示。比如 unsigned int 转 bool 没提示，也不知道怎么让它提醒。
CF1144E 想到了康托展开，但是没有发现是个 26 进制下的求平均值……
两个 int 的 pair 搞映射，可以合成一个 ll 丢进去，这样就可以用 unordered_map 加速了。
CF1204D 妙妙构造趣题
arithmetic progression：等差数列