简介 换根 DP 是解决当根节点变化时答案也发生变化的问题的题目，通常需要两遍 DFS，一遍先钦定一个点为根处理信息，第二遍是换根 DP。 [POI2008] STA-Station 给定一个 n≤106n\le 10^6n≤106 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 题目链接：P3478。 当根节点通过边 (fa,u)(fa,u)(fa,u) 转移时： ...

搜索关键词 给定 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章。 请问，其中有多少个单词在文章中出现了。 注意：每个单词不论在文章中出现多少次，仅累计 1 次。 题目链接：AcWing 1282。 类似 KMP 算法中的 next 数组，AC 自动机是在一个 Trie 树上进行匹配，模板串由一个字符串变为一个字符串集，这样一来 next 表示的含义就是当前结点对 ...

简介 借助左旋和右旋操作，在保证 BST 性质的情况下尽可能地减少树的高度。 当结点 x→y→zx \to y \to zx→y→z 呈直线形的时候，rotate(y),rotate(x)rotate(y), rotate(x)rotate(y),rotate(x)；呈折线形时，rotate(x),rotate(x)rotate(x),rotate(x)rotate(x),rotate(x)。可以 ...

莫比乌斯函数 首先给出莫比乌斯函数 μ(n)\mu(n)μ(n) 的定义： n=∏i=1kpiciμ(n)={0,∃ci≥2(−1)k,∀ci<2n=\prod_{i=1}^k p_i^{c_i}\\ \mu(n)=\left \{ \begin{aligned} &0,\exist c_i\ge 2\\ &(-1)^k,\forall c_i<2\\ \end{ali ...

简介 ST 表是用来解决重复贡献问题的数据结构，相较于线段树，它的初始化复杂度 O(nlog⁡n)O(n\log n)O(nlogn)，查询复杂度 O(1)O(1)O(1)，常数也更小，但无法修改。 重复贡献问题是指具有性质 f(x,x)=xf(x,x)=xf(x,x)=x 并且具有结合律的运算，例如最大值、最小值、按位与、按位或、GCD 等。 关于预处理 ⌊log⁡2x⌋\lfloor\log_ ...

公式 公式中 ∩i=1sAi\cap_{i=1}^{s}A_i∩i=1s​Ai​ 表示任意选 sss 个集合交起来。 ∣∪i=1nAi∣=∑s=1n(−1)s−1∣∩i=1sAi∣|\cup_{i=1}^nA_i|=\sum_{s=1}^n (-1)^{s-1} |\cap_{i=1}^{s}A_i| ∣∪i=1n​Ai​∣=s=1∑n​(−1)s−1∣∩i=1s​Ai​∣ 下面推导复杂度。从 n ...

高斯消元用来求解 n 个 n 元线性方程组，复杂度为 O(n^3)，通常是解决一些存在环的 DP 问题。

递推 给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cba mod (109+7)C_b^a \bmod (10^9+7)Cba​mod(109+7) 的值。 数据范围 1≤n≤100001\le n \le 100001≤n≤10000 1≤b≤a≤20001\le b \le a \le 20001≤b≤a≤2000 题目链接：AcWing 885。 复杂度：O(n2)O(n^ ...

欧几里得算法 辗转相除法，设 a≥ba\ge ba≥b 原理是： gcd⁡(a,b)=gcd⁡(b,a−b)\gcd(a,b)=\gcd(b,a-b) gcd(a,b)=gcd(b,a−b) 这个原因是 gcd⁡(a,b)∣a,gcd⁡(a,b)∣b\gcd(a,b)\mid a,\gcd(a,b)\mid bgcd(a,b)∣a,gcd(a,b)∣b，所以相减同样满足 gcd⁡(a,b)∣(a− ...

欧拉函数 对于正整数 nnn，欧拉函数 φ(n)\varphi(n)φ(n) 代表小于 nnn 的数中，所有与 nnn 互质的数的个数。一般认为 φ(1)=1\varphi(1) = 1φ(1)=1。 性质1 对于素数 ppp，1∼(p−1)1\sim (p-1)1∼(p−1) 都与其互质，所以 φ(p)=p−1\varphi(p)=p-1φ(p)=p−1。 性质2 对于互质的 m,nm,nm,n ...