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

之前的内容索引：

图论

DAG 上的路径覆盖

DAG 最小不相交路径覆盖：拆成出边入边，跑最大匹配，路径个数 $= n - $ 最大匹配。可以假装成一开始由 $n$ 条路径覆盖，每增加一个匹配就合并了一对路径。

DAG 最小可相交路径覆盖：先传递闭包，再跑上述内容。

BFS 与最短路

如果所有路径长度都一样，那用 BFS 是最好的，但是 BFS 不能处理路径长度不一样的情况。

欧拉回路的优化

欧拉回路是不是可以把已经进入栈的边删了？比如记录一个 cur 之类的，这样就是严格的 $\mathcal{O}(V + E)$ 了。

用了 cur 相当于动态删边，这样保证不会枚举到多余的边，保证复杂度正确。

2-SAT

LRJ 书上给的 2-SAT 代码并不是严格 $\mathcal{O}(n)$ 的，服了。真的 2-SAT 要用 Tarjan 的。

团

图是若干个团之并的充要条件是不存在某个三元组中有两条边（实际上就是要满足传递性）

网络流

流量上限很小的时候跑点数多的网络流复杂度是正确的，比如 2019 秦皇岛 E 的流量最大是 $1$，点数是 $10^5$。此处没有证明，需要研究。

神秘的 Dinic 优化：

根据容量二进制下 $1$ 的个数分组，每次只加入一段在同一组的跑最大流，跑 $\log W$ 次结束，据说复杂度是 $\mathcal{O}(VElogW)$ 的。
先不加反向边跑最大流，再加反向边跑最大流。

参考资料：https://www.luogu.org/problemnew/solution/P4722

特殊图上的 Dinic

Dinic 的容量全是 $1$ 的时候，在二分图上的复杂度为 $\mathcal{O}(V \sqrt{E})$。在没有任何性质的一般图上最坏为 $\mathcal{O}(V^2E)$。

匈牙利算法在二分图上采用邻接表的复杂度为 $\mathcal{O}(VE)$，某些题目给 $n \leq 10^3$ 也可以过，是因为边数一般也是这个级别。实际上是能卡成 $\mathcal{O}(n^3)$，但是不好卡（和卡 SPFA 的感觉差不多）。

字符串

SAM 上的 parent 树就是反串的后缀树

SAM 是个 DAG

要给 SAM 的 fail 树建出图时，注意用的是 f[] 数组而不是 ch[] 数组。

广义 SAM 貌似也可以不用特判已有的存在。如果现在在创建一个之前有过的节点，那么这个节点的 fail 会跳到之前那个节点上，并且无论从两个节点中的哪个开始往上跳，最后都会跳到早一点创建的那个节点。因此这样在统计贡献的时候，其实理论上没有问题。

只看 SAM 的 fail 树，则两个节点的 LCA 代表的是两个前缀（或子串）的 LCS，因此对于反串，它可以代表两个后缀的 LCP。

FFT 与多项式

FFT 的本质

我并没有搞懂 FFT 之后加一个常数是不是等于在原来的式子加一个常数？根据点值意义是这样的。但是如果加的不是一个常数是不是就莫得了？我对 FFT 的理解还不够深。

卷积套路

常见套路：将 $2^{ij}$ 的 $ij$ 拆成 $ij = \frac 12 [(i+j)^2 - (i^2 + j^2)]$，有 $2^{ij} = (\sqrt 2)^{(i+j)^2} \times (\sqrt 2)^{-i^2} \times (\sqrt 2)^{-j^2}$，这个形式可以卷积。

多项式 $\ln$

\[ [\ln f(x)]' \equiv \frac {f'(x)}{f(x)} \pmod {x^n} \]

\[ \ln f(x) \equiv \int \frac {f'(x)}{f(x)} \pmod {x^n} \]

只需要多项式求逆，复杂度 $\mathcal{O}(n \log n)$。

注意因为有积分，所以左右都是对 $x$ 求导（和牛顿迭代区分）。

多项式牛顿迭代

设 $g[f(x)] \equiv 0 \pmod{x^n}$，且在模 $x^{\lceil n/2 \rceil}$ 下的解为 $f_0(x)$，现在要求 $f(x)$，有：

\[ f(x) \equiv f_0(x) - \frac {g[f_0(x)]}{g'[f_0(x)]} \pmod {x^n} \]

注意对于给定多项式 $h(x)$，它在 $g[f(x)]$ 中最好是个常数项（或者好计算），比如计算多项式 $\exp$ 时令 $g[f(x)] = e^{h(x)} - f(x)$ 并不可做，但是 $g[f(x)] = \ln f(x) - h(x)$ 就很可做了。

以及 $g(x)$ 求导的时候，是对 $f(x)$ 求导而不是对 $x$，比如 $g[f(x)] = \ln f(x) - h(x)$，$g'[f(x)] = \frac 1{f(x)}$。注意因为是在 $f(x)$ 处展开，所以 $g(f(x))$ 是对 $f(x)$ 求导（和其他积分方法区分）。

多项式 $\exp$

用牛顿迭代过程会出现 $\ln$，时间复杂度 $T(n) = T(\frac n2) + \mathcal{O}(n \log n) = \mathcal{O}(n \log n)$。

其他多项式

设当前函数为 $f(x)$，要求 $g[f(x)] \pmod{x^n}$。若 $g'(x)$ 是个好算的多项式，那就可以如下操作：

\[ g'[f(x)] \equiv f'(x) \cdot g'[f(x)] \pmod {x^n} \]

\[ g[f(x)] \equiv \int f'(x) \cdot g'[f(x)] \pmod {x^n} \]

注意因为有积分，所以左右都是对 $x$ 求导（和牛顿迭代区分）。

因为求导和积分都很好算，乘法直接 FFT，其中 $g(x)$ 可以是反三角函数等。

数据结构

树

Prufer 序列

Prufer 序列性质：

$n$ 个节点的无根树的 Prufer 序列长度为 $n-2$。
Prufer 序列与无根树一一对应。
度为 $d$ 的点会出现 $d-1$ 次
Cayley 定理：$n$ 个点的完全图的生成树个数为 $n^{n-2}$ 个（考虑 Prufer 序列长度为 $n-2$，每个位置可以随便放点）。
设已知节点的度数组 $\{d_i\}$，则其无根树的数量共 $(n-2)! / \prod (d_i - 1)!$ 种（每个点出现 $d_i-1$ 次，考虑 Prufer 的全排列）

虚树

一般来说，我们建立虚树是只要树形结构的，因此加边的时候只加从父节点到子节点的边就好了，这样还可以省空间。

欧拉序与树上路径

对于欧拉序与树上路径的关系：

令 first (u) < first (v)，则

u, v 在一条链上，则路径为 first (u) -> first (v)
否则，路径为 last (u) -> first (v)，同时还要额外加上一个 LCA 处的信息，因为 LCA 并不会出现在序列中。

路径上的点只有出现奇数次的才能被统计。

子树问题

树上对子树的操作 $\rightarrow$ DFS 序列对区间的操作，只要能搞后者，那前者就是可搞的。

树分治

树分治中，每次找了 root 之后要再重新求一下 siz，否则记录的 siz 并不是以 rt 为根节点的时候的。

树分治为了保证复杂度，常用做法是把所有子树信息整合之后求一遍，再减去每个子树中重复的部分（而不是像背包一样，每次合并一个子树）。

但是后者用一些方法也可以保证复杂度。比如统计是否存在长度为 $K$ 的路径，则每次递归一个子树，就把路径信息丢到一个 set 里，对下一个子树的路径，查询这个 set 是否存在一个数与它加起来是 $K$，这样是稳定 $\mathcal{O}(n\log n)$ 的。

反之却不一定：如果 set 记录的是一个新子树的路径，每次用以前合并的子树查询，那时间可能会变成 $\mathcal{O}(n^2)$。总而言之就是，最好不要枚举以前合并的子树，要枚举也应该枚举新的子树，才是 $\mathcal{O}(n)$ 级别的。

数论

根据辗转相除法，可以认为 $(0, p) = p$。

$n! \cdot 2^n = (2n)!!$

计算

\[ \sum _{i=0}^n \sum _{j=0}^n (-1)^{i+j} \binom ni \binom nj (k-1)^{(i+j)n - ij} k^{(n-i)(n-j)} \]

其中 $n \leq 10^5$，模 $10^9+7$。

比较暴力的做法：

发现最后可以变成关于 $ij$ 的卷积，且最后会有 $a^{ij}$ 之类的项，拆成 $(i+j)^2, i^2, j^2$ 关系，即可用 MTT + 二次剩余，但是常数非常神秘。

比较正常的做法：

对于固定的 $i$，最后那一堆东西可以化成某个常数 $a$ 的幂 $a^j$ 和一个二项式系数 $\binom nj$ 的乘积的前缀和，这东西实际是个二项式展开 $(a+b)^j$，就可以做了。

主要就是看，如果固定了某个系数，那后面的部分是不是可以快速处理。以及，前缀和 + 组合数的前缀和形式，很有可能是某个二项式展开的形式。

另一个例题：

计算

\[ \sum _{i=0}^{\lfloor n/2 \rfloor} a^i b^{n-2i} \binom n{2i} \]

模 $p$ 的值，其中 $n, a, b, p \leq 10^{18}$。

\[ \begin{aligned} \sum _{i=0}^{\lfloor n/2 \rfloor} a^i b^{n-2i} \binom n{2i} &= \sum _{i=0}^n (\sqrt a)^i b^{n-i} \binom n{i} [i \bmod 2 = 0] \\ &= \sum _{i=0}^n (\sqrt a)^i b^{n-i} \binom n{i} \cdot \frac {1^i + (-1)^i}2 \\ &= \frac 12 \sum _{i=0}^n (\sqrt a)^i b^{n-i} \binom n{i} + \sum _{i=0}^n (-\sqrt a)^i b^{n-i} \binom n{i} \\ &= \frac 12 [(b + \sqrt a)^n + (b - \sqrt a)^n] \\ \end{aligned} \]

这个东西是两项递推的通式，特征根 $x_1 = b + \sqrt a,\ x_2 = b - \sqrt a$，可以据此得到递推的两个系数，矩阵快速幂。

要点：一些 $[expr]$ 也可以显式地构造出来。其他地方需要注意的转化和上述所说是一样的。

\[ \begin{aligned} \sum _{0 \leq i+j \leq n} \binom ai \binom bj &= \sum _{i=0}^n \sum _{j=0} ^{n-i} \binom ai \binom bj \\ &= \sum _{i+j=0}^n \sum _{j=0} ^{n-(i-j)} \binom a{(i+j)-j} \binom bj \\ &= \sum _{i=0}^n \sum _{j=0} ^{n-i} \binom a{i-j} \binom bj \\ &= \sum _{i=0}^n \binom {a+b}i \\ \end{aligned} \]

主要是利用了 $\sum _{i=0}^n \binom ai \binom b{n-i} = \binom {a+b}i$，想想组合数从前 $a$ 个东西和后 $b$ 个东西里共取 $n$ 个东西的组合意义就明白了。

威尔逊定理

$n$ 是素数，当且仅当 $(n-1)! \equiv -1 \pmod n$。容易发现这个东西对 $1$ 甚至也是合法的，但是写成 $n \mid (n-1)! + 1$ 的话就不合法了。

二项式展开

令 $f(x,\ y) = \binom {x+y}x a^x b^y$，则有 $f(x, y) = a \times f(x-1,\ y) + b \times f(x,\ y-1)$。

要点是注意杨辉三角中，系数的关系与二项式所带系数的关系，可以比较容易得到上式。利用这个东西可以维护一块连续的 $n$ 下，$\sum_{i = l}^r \binom ni a^i b^{n-i}$ 之类的式子。

动态规划

四边形不等式

四边形不等式小节：

区间包含单调性：若 $Y \subseteq X$，价值函数 $w$ 满足 $w(X) \geq w(Y)$，则 $w$ 满足区间包含单调性。
四边形不等式：价值函数 $w$ 满足 $w(X \cap Y) + w(X \cup Y) \geq w(X) + w(Y)$，则 $w$ 满足四边形不等式。

当 $f$ 过程取 $\min$，且价值函数 $w$ 满足上述两条，则 $f$ 满足四边形不等式。此时有：

2D1D 决策点：$h(l,\ r-1) \leq h(l,\ r) \leq h(l+1,\ r)$
1D1D 决策点：$h(i) \leq h(i+1)$

满足四边形不等式的函数类

$w_1, w_2$ 满足四边形不等式（或区间包含单调性），则其非负系数 $c_1, c_2 \geq 0$ 的线性组合 $c_1w_1 + c_2w_2$ 满足四边形不等式（或区间包含单调性）。
若存在函数 $f(x), g(x)$ 使得 $w(l,\ r) = f(r) - g(l)$，则函数 $w$ 满足四边形恒等式。当函数 $f(x), g(x)$ 单调增加时，函数 $w$ 还满足区间包含单调性。
若 $g(x)$ 是零阶导和一阶导都单增的函数，$w$ 满足上述两条，则 $g(w)$ 也满足上述两条。比如 $g(x) = x ^ 2$ 之类的情况，就可以用单调性解决（而避开斜率优化）了。
若 $g(x)$ 是仅有一阶导单增的函数，$w$ 满足上述两条，则 $g(w)$ 只满足四边形不等式。

转移单调性

一个转移单调性的代码分析：

void Cal(int n, ll x){
    static pint q[N];
    int top = 0, now = 0;
    q[++top] = ..

    for(int i=1; i<=n; i++){
        // 注意这里的写法，好好思考一下移动方式
        // 由于每次 i 能更新的区间都是 i 后面的，而 now 一定不在被更新的位置中
        // 因此每次 pop 掉一堆东西并不会影响 now 的位置	
        if(now < top && q[now+1].fi == i) now++;
        f[i] = F(i, q[now].se, x);
        g[i] = g[q[now].se] + 1;

        while(top){
            ll f1 = F(q[top].fi, q[top].se, x);		// top
            ll f2 = F(q[top].fi, i, x);			// now
            if(f2 < f1 || f2 == f1 && g[i] < g[q[top].se]) top--;
            else break;
        }
        // BSearch()
    }
}

筛法

杜教筛和 min25 筛是 $\mathcal{O}(n)$ 的，但是实际上需要开 $2\sqrt n$ 的空间。

\[\sum _{i=1}^{\sqrt n} \sqrt {\frac n{i^2}}\sim \mathcal{O}(\sqrt n \log n)\]

非常神秘，第一眼以为这个东西计算量会很大的。

\[ \mu^2(n) = \sum _{d^2|n} \mu(d) \]

神奇结论，不会证。

证法：https://www.cnblogs.com/hua-dong/p/9923022.html

离散数学

离散虚数

在 $\mathbb{Z}_p$ 下的虚数：$i \equiv \sqrt {-1} \equiv \sqrt {p-1} \pmod p$，需要二次剩余。

线性代数

高斯消元

写高斯消元的时候看清楚：

交换哪两行，不要看错
目前处理的是哪个变量，在加到另一行的时候不要写错

高斯消元模数不是质数时，采用辗转相除法进行消元。消元的目的其实是将该列的其他非零元素，通过线性运算变成 $0$。

假如当前准备用 $a_{i, i}$ 消 $a_{i, j}$，则每次辗转相除后有 $(a_{i, i},\ a_{i, j}) \rightarrow (a_{i, j},\ a_{i, i} \bmod {a_{i, j}})$，经过有限次计算必然能够让其中一个变为 $0$，就完成了对该行的消元。

这篇文章说得很好：这里直接把辗转相除看成一种把一个元素变成 $0$ 的过程即可。

环空间

如果两个环可以异或相消，则一个图中的所有简单环，可以由某个钦定的点 $u$ 为始末点的所有简单环组合得到。实现可以用 DFS，记录第一次访问到某个点时的路径异或值 $dis_u$，则每次访问到已经经过的点时，只需要把当前的异或值和 $dis_u$ 异或一下就成了一个环。显然，这样找到的环的个数是 $\mathcal{O}(V + E)$ 的。

仔细想想，上面的过程实际就是随便找了一棵生成树（DFS 树），然后把所有非树边和两点最短路径相连，就构成了一个基本环。如果相连的是一个树边也无所谓，反正绕成一圈之后就完全没贡献了。

这个是 WC2011 最大 XOR 和路径的结论，除此之外还有另一个结论：如果路径也可以异或，那么一条从 $u$ 到 $v$ 的路径异或上很多环，得到的仍然是一条从 $u$ 到 $v$ 的合法路径。

注意因为有重边，所以可以走回父亲的边…… 这个地方很容易出问题，因为不走回父亲的边会 continue，少计算一个可能有代价的环。

在上文所述的情况下，如果要你走一个以 $u$ 为始末点的环，那其实就是唬人的：如果环不经过 $u$，则从 $u$ 走到环上再走回 $u$ 后就满足条件了，且异或和相等。

关于 Cycle Space

具体来说，上文其实说明了这么一件事：一个图 $G$ 的满生成森林（Full Spaning Forest）加上任意一条不在森林中的边构成的环，形成了 F 的一个基础环（Fundamental Cycle of G）。其中，图 $G$ 的满生成森林是每个连通分量的任意一棵生成树构成的集合。

我们把图 $G$ 中与满生成森林 $F$ 关联的所有基础环的集合称为基础环系。设 $T$ 是连通图 $G$ 的一个最小生成树，则与 $T$ 关联的基础环系是圈空间 $W_c(G)$ 的一组基，且基的大小恰为 $m − n + c$，其中每个参数含义见下文。

This number is called the circuit rank of the graph, and it equals $m − n + c$, where $m$ is the number of edges in the graph, $n$ is the number of vertices, and $c$ is the number of connected components.

也就是说，一个连通分量中非树边构成的所有环，可以通过异或组合得到该连通分量的所有环，并且这些环恰好相互独立。我们把所有连通分量中基础环系的大小之和称为环秩（Circuit Rank）或环空间的维度（Dimension of Cycle Space）。显然，基础环系中构成的都是简单环，而通过基础环系组合出来的环可以不是简单环。

利用基础环可以化简回路方程。只要把回路中相互独立的方程组列出来，就是秩最小的方程组，这个只需要列出所有的基础环即可。

（以上部分内容由 @roife 翻译，部分来自 Wikipedia）

计算几何

杂项

三分

三分搞不清左右怎么移动时，就假设选出来的两个点 $x_1, x_2$ 都在 $x_0$ 的同一侧模拟一下。

带权二分

林克卡特树：删掉 $k$ 条边，再随便加 $k$ 条边权为 $0$ 的边，最大化直径。这东西应该能想到是最大化 $k+1$ 条不相交长链的和的…… 而不是贪心地选取 $k$ 个最小的边删掉，再在剩余边里求直径。

带权二分的往大取 or 往小取？需要想清楚。

括号序列

括号序列不能在有负边权的树上使用，因为不满足 LCA 的深度最小了。

一个左右括号个数相等的括号序列（不一定合法），写成前缀和形式后，对所有能取到最小值的位置经过轮换都是一个合法括号序列。

质数 gap 估计

质数 gap 的一些估计：

范围	$10^9$	$2^{32}$	$10^{18}$
gap	$\leq 300$	$\leq 360$	$\leq 1500$

LVG Lemma

下面内容并没有经过整理。

LVG Lemma 求 DAG 不相交方案数
这句话指出了啥时候能用来求不相交路径数
只有一颗的栗子 2019/9/30 14:24:47
卧槽
只有一颗的栗子 2019/9/30 14:24:54
要求可行排列唯一
原来如此，因为网格图上可行排列本来就是唯一的。。。
UESTC__DEFAULT hexisyztem 2019/9/30 14:25:46
我是个大瞎子
那要是可行排列不唯一求出来的是啥
UESTC__DEFAULT hexisyztem 2019/9/30 14:26:47
昨天在下面的证明里看了半天，看得脑壳疼
quailty 2019/9/30 14:26:54
求出来的就是那个 sum
quailty 2019/9/30 14:27:22
那个 signed sum
只有一颗的栗子 2019/9/30 14:28:07
哦LGV引理其实是说那个行列式可以用那个signed sum做计算是吧
quailty 2019/9/30 14:28:16
反了
只有一颗的栗子 2019/9/30 14:28:28

14:28:30
只有一颗的栗子 2019/9/30 14:28:30
哦
quailty 2019/9/30 14:28:36
是那个 signed sum 可以用行列式算
UESTC__DEFAULT hexisyztem 2019/9/30 14:28:36
那个signed sum计算复杂度太高了
quailty 2019/9/30 14:28:49

只有一颗的栗子 2019/9/30 14:28:52
所以说只有排列唯一的时候，signed sum有了组合意义
只有一颗的栗子 2019/9/30 14:28:59
soga
只有一颗的栗子 2019/9/30 14:30:07
哦signed sum是指数的，行列式是多项式的

位运算

对于 $x, y > 0$，$x \oplus y > x$ 当且仅当 $y$ 的第 $\mathrm{highbit}(x)$ 位为 $1$。

如果 A 是均匀分布，B 不是均匀分布的话，A xor B 的结果是依然是均匀分布。

好像可以用来求一个 [1, n] xor 不规律数列的结果。

$[0, n] \oplus x$ 得到的所有数可以分成 $\mathcal{O}(\log n)$ 段连续的区间：从高到低按位考虑分解 $n$，则某一位 xor 后只影响了该位的 $01$，且它右边的数虽然也 xor 了一个值，但是这部分的取值恰好是连续的，可以据此分段。

参考异或询问。

小技巧

有时候题面没有想法，可以看看数据范围，数据范围或许提供了特殊的提示。比如：

Hamiltonian Path：$(u, v)$ 保证 $u < v$ 使得哈密顿回路只有 $1 \rightarrow 2 \rightarrow \ldots \rightarrow n$
Ghh Matin：数据范围表明至少有一个置换的阶大于 $\frac n2$，因此才可以不重不漏地计算。

https://ac.nowcoder.com/acm/contest/1111/B https://www.zhihu.com/question/47247118

对于 “先抽完某个东西”，可以转化成 “后面还有其他东西” 之类的。可以假设最后抽到了 A，接着去掉所有的 A，再考虑剩余部分最后抽到的是 B，去掉 B…… 以此类推。

bitset 用来匹配字符串有意想不到的效果！其实就是依次检验模板串 $s$ 的某一位是否和当前串 $t$ 的一样，只有每一位都一样，才认为匹配上了。bitset 优化的就是 “批量检查是否匹配上” 的这个过程。

如果要统计以每个 $i$ 为左端点区间的信息，且这个信息只和 $i$ 之后的东西相关，那就考虑倒序插入 $i$，动态维护。

比如给两个序列 $\{a_n\}, \{b_n\}$，对每个位置 $i$ 求 $\sum _{j=i}^{b_i} \max \{a_j, a_{j+1}, \ldots, a_{b_i}\}$，就可以倒序插入位置，每次给 $a_i$ 作为最大值能更新到区间进行整体置值，查询的时候求 $[i, b_i]$ 区间和即可。

平面内互不相交的两个矩形，一定存在一个横向或纵向分割线，将它们恰好分在两侧。这个性质可以用来 DP。

生成一个括号序列：

// rebuild [l, r) and make it still balanced
void Rebuild(int s[], int l, int r){
    srand(time(0));
    std::random_shuffle(s + l, s + r);
    int sum = 0;
    for(int i=l; i<r; i++){
        sum += s[i];
        if(sum < 0 || sum == 0 && s[i] == 1) s[i] *= -1;
    }
}

只要往里传入一个合法括号序列，出来的东西就可以替换掉原来的序列。

代码上的问题与可能的犯蠢

递归里面用 vector 好像因为要恢复现场而常数巨大…… 即使 reserve 了也没有太大优化。

推式子的时候认真一点，尤其是把类似 $\lfloor m/g \rfloor \rightarrow m$ 这种操作的东西直接写在草稿纸上的时候，注意是不是会影响其他参数。比如这样子改了 $i$ 的枚举范围后，用到原来 $i$ 的值实际应该是 $ig$，这里很容易疏忽。

2019 ICPC 南京总结：

抄板子的时候复制粘贴一行，里面的变量要改

区分好 $n$ 和 $m$、$i$ 和 $j$ 等变量，不要写混。抄板子的时候也是。

DFS 在直接 return 之后要记得恢复更新过的状态（比如 vst 或 dis）

NO YES 注意大小写。

1	const int MOD = 0x3f3f3f3f;

我杀我自己

const int SQRT2 = 116195171; const int INV_SQRT2 = 557219762;

有些编译器自动加 -O2，需要开 -O0 使 gdb 可以正常调试。

二分写成 M = L + (R-L) / 2 可以处理负数的情况

set 要用 .lower_bound 才是正确的，但是 lower_bound() 貌似就是 $\mathcal{O}(n)$，且在 C++14 之后才相同。

快速幂其实都有点 bug，比如求 $1^0 \bmod 1$，大部分返回的都是 $1$ 而不是 $0$，需要注意。

写成 return ret % MOD; 就行。

快速幂应当特殊处理底数模模数 $bas \equiv 0 \pmod p$ 的情况，模意义下我们最好认为 $0 ^ 0 \equiv 0 \pmod {p}$，并且需要特殊处理，不然快速幂过程可能出现 $(10^9+7) ^ {10^9 + 6} \equiv 1 \pmod {10^9 + 7}$ 这种神秘错误结果……

一个坑点：x % 2 == 1，当 $x < 0$ 时得到的是 $-1$ 而不是 $1$。

map 中不存在的元素 $x$ 虽然默认第二维是 $0$，但是每次查询的时候貌似就会真的创建一个 $(x, 0)$ 的 pair，进而可能发生 MLE。所以还是不要偷懒，写下 .count() 的比较好……

if(i & 1 == 0) 的作用可能和我想的不一样。注意位运算优先级。

C 里面的 ull 输出格式是 llu——d 和 u 对应。

写线段树还是特判一下 L > R 的情况好了，不然你永远不知道你在什么位置丢入了错误的参数而导致 RE……

写凸包之类的题，维护的时候一定要 while(..) q.pop()，而不是用 if(..)。用一个小时的垃圾时间找到了这个 bug，下次要记住了。

multiset 的 count 操作复杂度是和查询的元素个数相关的，所以全都是一个元素的时候，count 可能会爆炸……

按照虎哥哥的话来说，用 .find() != .end() 是个好习惯。

好题收集

折半枚举妙妙题：2016 CCPC Hangzhou Onsite D

一个有必要记录一下的题目：https://codeforces.com/contest/1237/problem/F

可以假设选了 $i$ 个横的，$j$ 个纵的，那总占用的行列数就确定了，并且还有性质：对于横着放的多米诺骨牌来说，如果其占用的 $1$ 行 $2$ 列的位置都确定了，那么它的所有位置也确定了。如果我们选好了这样的 $1$ 行 $2$ 列，只要把 $2$ 列进行全排列，就能不重不漏地得到所有可能的放置交点。列也同理。

这个性质使得我们可以按行列分开 DP，很妙。

一个有点意思的题目：给一个序列 ${a_n}$，划分为 $p$ 段，每一段 $[l, r]$ 的价值定义为

\[ (\sum _{i=l}^r a_i) \bmod p \]

最大化序列价值。

考虑 $f(n, k)$ 表示前 $n$ 个划分 $k$ 段的方法，有

\[ \tag{1} f(i, k) = \max _{j < i} \{f(j, k-1) + (s_i - s_{j-1}) \bmod p\} \]

其中 $s_i$ 是 $a_i$ 的前缀和。拆开后面一项，对 $s_i \geq s_{j-1} \pmod p$ 有

\[ \tag{2} f(i, k) = \max _{j < i} \{f(j, k-1) - s_{j-1} \bmod p \} + s_i \bmod p \]

显然 $f(j, k-1) - s_{j-1} \bmod p$ 只和 $j, k$ 相关，因此可以用一个数据结构维护一下所有 $s_i \geq s_{j-1} \pmod p$ 的这个最大值，每次转移 $(1)$ 式的时候查询一下就行。

对于 $s_i < s_{j-1} \pmod p$ 的部分只比 $(2)$ 式需要多添加一项 $p$，也很好维护。

2019 银川 ICPC - E：一个有点东西的转化题，主要把异或平方按位拆开，接着考虑贡献。

一道比较有意思的 DP 题目：Beautiful Bracket Sequence。DP 中有一定容斥和讨论，但是还是很妙。

一个很神秘的三元环定向问题：[WC2007] 剪刀石头布。主要思路是统计不合法的三元环，并将其对应上一个点的两条出边。通过这样转换，可以得到一个随着出度 $x$ 增加的函数 $f(x)$，且 $f(x)' > 0$，这给费用流提供了条件。

另外，本题的建模值得再多看几次。

二进制分组构造好题：SmartGarden。只要发现连边的东西，是除了最后一位，其他位至少有一位不同的，就可以按位批量连边了。一个可能的题解：https://www.cnblogs.com/sjkmost/p/11953476.html

CF 1292C

关于一个树上 mex 的推论：

\[ \begin{aligned} S &= \sum_{1 \leq u < v \leq n} \mathrm{mex}(u, v) \\ &= \sum_{1 \leq x \leq n} \left( \sum_{\mathrm{mex}(u, v) = x} x \right) \\ &= \sum_{1 \leq x \leq n} \left( \sum_{\mathrm{mex}(u, v) \geq x} 1 \right) \\ &= \sum_{1 \leq x \leq n} f(x) \\ \end{aligned} \]

其中 $f(x)$ 是满足 $\mathrm{mex}(u, v) \geq x$ 的二元组个数。

记录一个奇怪的 SAM 题目：卡拉巴什的字符串。

给一个串，求对于每个前缀 $\mathrm{pre}(n)$，$\mathrm{mex} \{ \mathrm{LCP}(\mathrm{suf}(i),\ \mathrm{suf}(j)) \mid 1\leq i < j \leq n \}$ 的值。

考虑 SAM 的插入过程。假设当前串插入到了 np，则 np 在 fail 树的父亲 pa，一定与 np 存在一个共同的 right 位置 $e_1$，与一个不同的 right 位置 $e_2$，此时 $\mathrm{LCP} (\mathrm{suf}(e_1 - \mathrm{len}(pa) + 1),\ \mathrm{suf}(e2 - {len}(pa) + 1)) = \mathrm{len}(pa)$ 是显然的：它们有一个长为 $\mathrm{len}(pa)$ 的公共前缀，且 $e2$ 是字符串末尾，不可能有更长的公共部分。并且注意到，如果同时将这两个对应后缀的起始位置往后移一位，可以得到所有其他更小的 LCP。

据此，我们得到重要结论：

引理 1：新插入节点 np 在 fail 树上的父亲 pa 加入了 LCP 在 $[0, \mathrm{len}(pa)]$ 的值。

现在的问题是：如果继续往后增加节点，之前加入的值还能保持吗？考虑串 $a_1a_2$ 加入 $b$ 变成 $a_1a_2b$ 的情况，显然之前可以选择 $a_1a_2$ 与 $a_2$ 作为选定后缀，并且在加入 $b$ 后，它们的 LCP 没有改变。如果加入的是 $a_3$，则 LCP 值会发生改变，这个改变会在本次插入新节点 np 的时候统计出来。因此我们有：

引理 2：若新插入字符 $c$ 改变了已有的 LCP，则改变量会在新插入节点 np 处计算出来，否则不改变原有的 LCP。

考虑 SAM 在插入 np 节点时，不满足 $\mathrm{len}(q) = \mathrm{len}(p) + 1$ 的处理方法。此时相对于 pre 的祖先链来说，原有的 p 及其之上的节点都会变成 nq 及其之上的节点，而 $\mathrm{len}(nq) = \mathrm{len}(p) + 1$，也就是说加入新节点不会让 mex 值下降，这与 mex 的性质是相符的。

综上，我们只需要在每次插入新节点后，记录其父亲的最大长度即可。需要特殊处理根节点：根节点要有两个儿子节点才能有 $\mathrm{LCP} = 0$。

这个题目说明了后缀的前缀和前缀的后缀确实是可以在一定程度相互转化的……

记录一个很妙的题

https://ac.nowcoder.com/acm/contest/4120/C

通过反向添加负权值，使得区间的后效性变得可撤销和可计算，因此让区间彼此独立了。如果你看到这里，我建议你再重新复习一遍本题以加深印象。

https://codeforces.com/contest/1290/problem/C

记录一个带权并查集的题目。

注意到每个点只会出现在两个集合，且有一些 “某个集合必选”“某个集合必不选”“某两个集合都选或都不选”“某两个集合必一个选一个不选” 的条件，那就可以变成并查集维护选或不选的状态了，并且设选中集合的点权值为 $1$，不选集合的点权值为 $0$，在每个联通块里选总权和较小的那个即可。

如何处理 “某个集合必选” 这类条件呢？可以令不选集合的点权值为 $\infty$，就相当于强制选择了那个集合。这个想法还是很妙的。

CF GYM - 102302I

动态随机插入维护上凸包。维护的时候需要注意的事情：

按 $x$ 递增，$y$ 递减的方式排序。
先不插入点，考虑将插入点左右的位置，用叉积判断是不是需要删除。注意删除之后迭代器可能会发生变化，要重新找一次插入点。
判断在凸包内外时，比较插入位置前后的连线与插入点的关系，再决定要不要插入。
（只适用于本题）需要额外考察凸包两端点的斜率。

写起来需要注意很多细节的题目，练一练能够提升对维护过程的理解。

记录一个好题：ARC 084 D

给定 $n \leq 10^5$，求它的倍数 $kn$ 的最小数位和。

这个题目竟然可以用最短路解。考虑限制条件即为 $kn \equiv 0 \pmod n$，因此我们只需要找到一个模 $n$ 为 $0$ 的数 $x$，且 $x$ 的数位和最小即可。

假如我们知道了 $x$ 的数位和，则从 $x \rightarrow x+1$ 会让数位和增加 $1$（暂时忽略进位的情况），从 $x \rightarrow 10x$ 不会增加数位和。因此我们可以在模意义下给 $0, 1, \ldots, k-1$ 分别增加边 $(x,\ x+1)$ 与 $(x,\ 10x)$，并设边权分别为 $1$ 和 $0$，跑一个到 $0$ 的最短路即可。这个时候重新考虑进位的情况：虽然过程中增加了一些冗余的边，但是进位会在乘 $10$ 的边上计算，因此实际不会有问题。

初始条件是 $\mathrm{dis}(1) = 1$。

DP 计算一个不含 $k$ 的一个排列作为子串的、长度为 $n$ 的序列，则状态可以设置为 $f(i, j)$，表示当前长度为 $i$，且后 $j$ 个字符两两不同，但后 $j+1$ 有恰好一个相同的。用这个状态来表示就可以忽略掉其中每个字符具体是什么了。

原题是 ARC 100 F。

CF 1299D

https://codeforces.com/blog/entry/73664?#comment-579444

评论区给了一个很好的思路，在这里记录一下。

先说一下我们要做什么：我们有一些连接向 $1$ 的边，可以选择保留或者删除，想知道在不同保留或删除的情况下，形成每种环空间的方案数分别是多少（这题里最多只有 $374$ 种环空间的子空间）。

现在的做法是，我们钦定一条连向 $1$ 的边是树边，其他没钦定的、连向 $1$ 的边都是非树边，每次转移可以选择加入或者不加入某条非树边。显然，加入一条非树边时，需要知道它在树上构成的环的大小，并加入集合。但是如果我们多用一维记录当前作为树边的是哪个点，复杂度就会大大上升。

一个很厉害的 idea 出现了：不考虑加入树边的具体的是哪个点，而是在树里再钦定一个点 $x$，则通过树边到达 $x$ 和通过当前的非树边到达 $x$ 的两个路径形成的闭环，必然不属于当前的环空间（因为它带来了一条非树边，且画图可知通过树边到达 $x$ 的有效异或路径上，是不会偶数次经过那个非树边的），等价于加入了上文提到的环。

也就是说，我们维护环空间的时候，插入的可以不一定是树与非树边 $e$ 构成的环。只要插入的环中经过奇数次我们即将插入的边 $e$，也就是保证这个环之前并不在环空间中，就可以了，而这个过程可以用钦定一个点实现。很妙。

图论