长链剖分
长链剖分回顾注意到，有一个和它名字特别相近的算法叫做 重链剖分。它是每一次找到大小最大的儿子作为重儿子，这样树的规模就至少缩小了 $\frac{1}{2}$，于是从底部的某一个节点到达根节点的重链数量最多也就 $O(\log n)$ 个。
它可以帮助我们解决很多问题。比如说我们要在树上维护路径加路径求和，那么就需要它帮助我们在 $O(q \log ^2 n)$ 的复杂度内完成题目。
正文定义作为一个较为重要的辅助工具，我们需要一些定义：
重儿子： 最大深度最大的一个儿子。形式化的，$son_u = \operatorname{Id} (\max\limits_{v\in son_u} len_v)$，其中 $len_u$ 表示 $u$ 子树中的最大深度。
重边： 一个点到它重儿子的那条边叫做重边。形式化的，集合 $E = { (u, son_u)}$ 的元素叫做重边。
重链的顶端： 若一个点 $u$ 不是它父亲的重儿子，那么它是一条重链的顶端。形式化的，集合 $V = {u\mid u \not = son_{fa_u}}$ 中的点叫做重链的顶 ...
6.8 模拟赛题解
6.8 模拟赛题解A. Cut Ribbon (CF189A)Des给定四个数 $n,a,b,c$，要求把 $n$ 长度的绸带划分为若干段，每一段的长度必须是 $a,b$ 或者 $c$。求最长的划分段数。
Sol显然，我们设 $f_i$ 表示前 $i$ 的长度最长能分多少段，然后显然有：
$$\left{\begin{matrix} &f_i = f_{i-a}+1, \text{if } i\ge a \& f_i=f_{i-b}+1, \text{if }i\ge b \& f_i=f_{i-c}+1,\text{if }i\ge c\end{matrix} \right.$$
于是这道题就做完了。复杂度 $O(n)$。
B. Boredom (CF455A)Des给定一个数列 $a_n$，要求进行若干次操作。每次操作选择一个数 $a_k$，删除所有等于 $a_k-1$ 和 $a_k+1$ 的数，并且获得 $a_k$ 的收益。求最大收益。
Sol关于我刚开始读错题了以为删除 $a_{k-1}$ 和 $a_{k+1}$ 这件事显然 ...
虚树
虚树 (Virtual Tree) 引入 消耗战有 $n$ 个点的树和 $m$ 次询问，每次询问先给出一个 $k$，然后给出 $k$ 个数，分别为 $h_i,i\in [1,k]$。求将这些给定点与 $1$ 号点分离的代价。这过程中只允许删除边，并且删除 $(u,v)$ 之间的边需要 $w$ 的代价。
$1\le n\le 2.5\times 10^5$，$1\le m\le 5\times 10^5$，$\sum\limits k\le 5\times 10^5$。
朴素做法不妨称每次询问给出的点为 关键点，考虑动态规划。
设 $f_u$ 表示隔离以 $u$ 为根节点的子树需要的代价，于是不难得出以下状态转移：
如果 $u$ 是关键点，那么删除 $\min\limits_{v\in fa_u}{(u,v)}$ 这条边，并加上代价。
如果 $u$ 不是关键点，那么获得 $\min{\min\limits_{v\in fa_u}{(u,fa_u)},\sum\limits_{v\in son_u}f_v}$ 的代价。
但是这样每一次动态规划是 $O(n)$ 的，显然无法满足我们的 ...
5 月 21 号模拟赛题解
5.21 Contest 题解A. Permutation
给定四个数 $a,b,c,d$ 求
$$\gcd(\prod_{i=a}^bi,\prod_{i=c}^di)$$
其中这样的询问有 $T(T\le 10)$ 次。$a,b,c,d \le 10^7$。
考虑最大公倍数的另一种形式，如果
$$a=\prod p_i^{\alpha_i}, b=\prod p_i^{\beta_i}$$
则：
$$\gcd(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}$$
于是，我们考虑对于每个质数，处理出来 $a!,b!,c!$ 和 $d!$ 有几个该质因子，然后 $\gcd$ 的质因子数量就是 $\min(b-a,d-c)$。
复杂度就是 $O(N+T\sum\limits_{p\in \mathcal{P}}\log_p N)$，是要严格小于 $O(NT)$ 的。这是因为质数一共只有 $\ln$ 个，但是质因子数量每次的底数都在增长。
B. Tree
给定一棵树，每个点有点权，删去一条边的代价是每个边 ...
01-trie
01-Trie介绍$01-Trie$ 是一类解决有关异或问题的工具。它支持插入、删除、全局 $+1$、求异或和、求最大异或值的问题。
异或和 $01-Trie$插入，删除操作首先我们明确 $01-Trie$ 的基本形态。它类似于一个动态开点线段树。每个节点有两个儿子 $t_{p,0}$ 和 $t_{p,1}$ 分别表示下一位是 $0/1$ 的编号是多少。这里我们的 $Trie$ 树维护的二进制串是从最低位开始的。而我们需要维护三个信息：
$t_{p,0/1}$，表示下一位是 $0/1$ 时的儿子编号是多少。这与普通的 $Trie$ 相同。
$w_p$，表示最后落在 $p$ 子树内的数有多少个。也可以理解为经过 $(p,fa_p)$ 这条边的数的数量。
$sum_p$，表示 $p$ 子树内的异或和。注意这里以 $p$ 为根节点就不需要考虑 $p$ 以上的部分，也就是原来 $11010$ 的东西现在可能是 $01011,1011,011,11$ 或者 $1$。
对于最终的异或和的答案，我们只关心在某一条 $1$ 边，它的 $w$ 是多少。因为只有权值是 $ ...
快速傅里叶变换
快速傅里叶变换（FFT）复数基本定义我们对于实数域 $\R$ 进行扩充，因为我们注意到对于方程 $x^2=-1$，我们无法在 $\R$ 内无法找到一个解。但是，我们总是相信一个 $n$ 次方程 $f_n(x)=0$ 总会有 $n$ 个解。因此，我们对于实数域进行扩充，计 $i^2=-1$，即可以用 $z=a+bi$ 的形式来描述一个数，我们称这样的数叫做 复数 (Complex)，记作 $\Complex$。
对于一个新的数域，我们需要定义一个加减乘除与之对应，特殊地，对于 $b=0$ 的情况，也即 $z\in \R$ 时，需要满足实数和复数在这些运算上的一致性，同时，我们也希望复数的加减乘除满足交换、结合律等法则。
于是，我们得到了定义：
$z_1=a+ bi,z_2=c+ di$，则 $z=z_1\pm z_2=(a+ c)\pm(b+ d)i$。
$z_1=a+bi,z_2=c+di$，则 $z=z_1\cdot z_2=(a+bi)\cdot(c+ ...
快速数论变换
快速数论变换 ——将单位根换成原根的快速傅里叶变换
原根 阶
前置：欧拉公式
对于 $a\in Z,m\in N^*$，若 $\gcd(a,m)=1$，则有
$$a^{\varphi(m) }\equiv 1\pmod{m}$$
这其实是对 费马小定理 的推广。费马小定理指出了 $m\in \mathcal{P}$ 时的特殊情况，即 $a^{m-1}\equiv1\pmod m$。
由欧拉公式，我们知道对于 $\gcd(a,m)=1$，一定存在 $x$ 使得 $a^x\equiv 1\pmod m$。那么，我们称最小的这个 $x$ 为 $a$ 模 $m$ 的阶，记为 $\delta_m(a)$ 或 $ord_a(m)$。
这阶具有以下几条重要性质：
性质 $1$$a^1,a^2,a^3,\dots,a^{\delta_m(a)}$ 在 $\bmod m$ 的意义下两两不相等。
证明
考虑反证法。若存在 $p,q\le \delta_m(a)$ 使得 $a^p=a^q$，则有：
$$a^{|p-q|}\equiv 1\pmod m$$
而这里显然 $ ...
网络流
网络流基本概念我们现在有一张图 $G={V,E}$，对于每一条边 $e\in E$，我们用 $(u,v,w)$ 来描述它，分别代表起点，终点和边权；并且这张图上有一个起点 $s$ 和一个终点 $t$，那么我们就可以称这个图是一张 网络。
另外的，对于这个起点 $s$，我们称之为 源点，对于终点 $t$，我们称之为 汇点。下面讲网络流几个基本概念。
弧对于每一条边 $e=(u,v,w)\in E$，我们称之为 弧。而这里的 $w$ 被称为这条弧的容量。
流对于一条 $u\to \dots \to v$ 的简单路径，我们称这是这张网络的一个 流。它满足以下性质：
对于流 $v_1\to\dots\to v_n$，它的大小必须小于等于 $\min\limits_{i=1}^{n-1}{w_{(v_i,v_{i+1})}}$。也就是说，流的大小小于等于路径上所有容量的最小值。
对于除源点和汇点之外的所有节点，总满足流进总流量等于流出总流量。
对于一张网络，我们希望给定一个确定的流，使得汇点的流量最大，这个问题叫做 最大流问题。
割对于一个网络 $G= ...
自动机
自动机
什么是自动机
对于一个字符串问题，我们需要设计好一种状态集合以及转移集合，使得对于给定字符串 $s$，我们只要把它扔进自动机里面就可以跑着跑着跑出我们需要的答案。
DFA（确定有限自动机）我们来看一个简单的小问题：求一个字符串中 a 字符的个数。
显然，对于这个问题，我们枚举字符串然后加一个 if 判断就可以 $O(n)$ 解决。但是我们希望把底层逻辑抽象出来，然后进行整理分析来得到更加复杂问题的求解。
显然，我们可以有很多状态。我们不妨设状态 $q_i$ 表示现在字符串内有 $i$ 个 a。那么，我们就可以画出一个自动机的图来：
我们放一个字符串进去，比如 $abbbabbab$，那么当遇到一个字符的时候，我们就会按照该字符是什么来决定下一步走到哪个状态。初始状态 $s_0=q_0$，结束状态 $q_i$ 就代表了答案 $i$。例如，我们演示一下过程：
首先，我们在 $q_0$，下一个字符是 $a$，于是走 $a$ 路径到达 $q_1$，然后后面的三个 $b$ 走 $b$ 路径，一直停留在 $q_1$。再接下来一个 $a$ 到达 $q_2$，一直循规蹈矩，最终走 ...
后缀数组
后缀数组 这真的是一个极其恶心而又难以理解的东西。
定义首先，对于一个字符串 $s=s[1\dots n]$，一个后缀 $i$ 被定义为 $s[i\dots n]$。
我们记录两个数组 $sa$ 和 $rk$，分别表示：
$sa_i$ 表示对所有后缀排序之后，第 $i$ 名的后缀下标是多少。
$rk_i$ 表示对所有后缀排序之后，后缀 $i$ 的排名是多少。
其中 $sa$ 被成为后缀数组。
由此我们不难看出，如果将 $sa$ 和 $rk$ 看成两个函数，其中 $f(x)=sa(x)$，那么 $f^{-1}(x)=rk(x)$。也就是说，他们两个互为反函数。
下面给出一张图来方便理解这个两个数组：
对于字符串 $s=\text{“aabaaaab”}$，它的所有后缀可以表示为 $\text{aabaaaab}$，$\text{abaaaab}$，$\text{baaaab}$，$\text{aaaab}$，$\text{aaab}$，$\text{aab}$，$\text{ab}$，$\text{b}$。将它们按照字典序排序，那么不难得到 ...