$ \varphi \times 1=id $

$ μ \times id=\varphi $

$ μ \times 1=\varepsilon $

$ \varepsilon \times1 =1 $

$ \sum _{i=1}^{n}\sum_{d|i}{d\cdot\varphi(d)}=\sum _ {i=1}^{n}\sum _{d|i}(\frac{i}{d})\cdot \varphi(\frac{i}{d})=\sum_{i=1}^{n}\sum_{\frac{i}{d}=1} ^{\lfloor\frac{n}{i}\rfloor} (\frac{i}{d})\cdot \varphi(\frac{i}{d}) =\sum_{i=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}{d\cdot\varphi(d)} $

一.最小树形图

1. 基础

1. 定义

   最小树形图,就是给有向带权图中指定一个特殊的点 $ root $ ,求一棵以 $ root $ 为根的有向生成树T,并且T中所有边的总权值最小。

2. 朱刘算法

1. 复杂度 $ O(VE) $

2. 算法流程

   1. 对固定根 $ root $ 进行一遍 $ DFS $ 判断是否存在最⼩小树形图。

   2. 为除了了 $ root $ 之外的每个顶点选定一条最小的入边(用 $ pre[u] $ 记录顶点 $ u $ 最小入边的起点)。

   3. 判断2中构造的⼊入边集合是否存在有向环,如果不不存在,那么这个集合就是该图的最
      ⼩小树形图。

   4. 如果3中判断出现有向环,则消环缩点。设 $ (u,v,w) $ 表示从 $ u $ 到 $ v $ 的权为 $ w $的边。

      假设3中判断出的有向环缩为新顶点 $ new $ ,若 $ u $ 位于环上,并设环中指向 $ u $ 的边权是 $ ω[u] $ 。

      那么对于每条从u出发的边 $ (u,v,w) $ ,在新图中连接 $ (new,v,w) $ ,对于每条进⼊入u的边 $ (in,u,w) $ ,在新图中建⽴立边 $ (in,new,w-ω[u]) $ 。

      新图⾥里里最⼩小树形图的权加上旧图中被收缩的环的权和,就是原图中最⼩小树形图的权值。重复2,3,4。

   5. 中判断⽆无有向环,返回权值。

3. 平面图

二.字符串

1. AC自动机

2. 后缀自动机

1. 自动机：

   1. 构成：

      1. $ alpha $ : 字符集

      2. $ state $ : 状态集合

      3. $ init $: 初始状态

      4. $ end $ : 结束状态集合

      5. $ trans $ : 状态转移函数

      6. $ trans $ 函数

      $ trans(s,ch) $ 表示当前状态是 $ S $ ,读入字符 $ ch $ 后的状态

      $ trans(s,str) $ 表示当前状态是$ S $ ,读入字符串 $ str $ 后的状态

      1. 杂项

      自动机A能识别的字符串就是所有使得 $ trans(init,x)∈end $ 的字符串x即为 $ Reg(A) $

      从状态S开始可被识别的字符串集合记为 $ Reg(S) $

2. 后缀自动机

   1. 定义

      给定字符串 $ S $

      $ S $的后缀自动机(SAM)是能够识别所有 $ S $ 的所有后缀的自动机

      即 $ SAM(x)=True $ ,当且仅当 $ x $ 是 $ S $ 的后缀

   2. 最简单的实现

      后缀树:将所有后缀插入trie中

      $ O(n^2) $

      太菜了

   3. 最简状态后缀自动机

      1. 大小是线性的

      2. 假如我们得到了最简状态后缀自动机SAM

         $ ST(str)=trans(init,str) $

         令母串为S,他的后缀的集合为 $ Suf $ ,他的连续子串的集合为 $ Fac $

         从位置 $ a $ 开始的后缀为 $ Suffix(a) $

         $ S[l,r) $ 表示S中 $ [l,r) $ 区间构成的子串

         下标从 $ 0 $ 开始

         对于字符串 $ x $ ,若 $ x $ 不属于 $ Fac $ ,那么 $ ST(x)=null $

         对于字符串 $ x $ ,若 $ x $ 属于 $ Fac $ ,那么 $ ST(x)!=null $

树分治

1.分治

1. 分治要求

   1. 问题缩小到一定规模是就可以容易的解决

   2. 该问题可以分解为若干个规模较小的相同问题，即用最优子结构的性质

   3. 利用该问题分解出的子问题的解可以合并为该问题的解

   4. 该问题所分解的各个子问题是相互独立的，不包含公共子问题

2. 树

1. 树的定义

   没有环的连通图

2. 性质

   1. 去掉树的一条边后所得的图不连通

   2. 在树中添加一条边后所得的图一定存在环

   3. 每一对顶点U V间有且仅有一条路径

3. 点分治

1. 基本方法

   首先选取一个点将无根树转为有根树，在递归处理每一颗以根节点的儿子为根的子树

2. 例题

   1. POJ1741

      求树上距离小于等于K的点对有多少 (N<=10000)

       点分治+DP
      

   2. BZOJ2599

4. 边分治

1. 基本方法

   自己YY

2. 例题

   1. QTREE4
      或BZOJ1095(题意相同)

5. 基于链的分治(树链剖分)

1. 题目：[Query On a Tree]

略

1. Astar2008 黑白树

2. QTREE4

6. 基于询问的分治 (CDQ分治)

1. BZOJ2001

7. 模拟退火

数论

1. 模方程

1. 线性同余方程

2. 线性同余方程组

3. 主要内容

   1. 考虑形如 $ a^b\equiv c \mod m $ 的方程

下文模方程均为 $ f(x)\equiv 0 \mod m $

1. 非线性同余方程

   1. 因式分解

2. 离散对数问题

   1. 考虑 $ f(x)=a^x+c $ ,则问题演变为离散对数问题

   2. 求解方法

      1. m为质数

      2. a和m互质

      3. 一般情况

2. 原根

1. 定义

   考察方程 $ a \cdot x ≡1(mod m) $，若 $ gcd(a,m)=1 $ ，则方程一定有解 $ x=\varphi(m) $

   我们定义在上述情况下，方程最小的解为 $ x=δ m (a) $ ，

   则显然有 $ δ m (a)≤φ(m) $ ，若a满足条件 $ δ m (a)=φ(m) $ ，我们就称a是模m的原根

2. 群论

   1. 定义

      G={S,⊕}

   2. 性质

      1. 封闭性

      2. $ a⊕(b⊕c)=(a⊕b)⊕c $

      3. 存在单位元

      4. 存在逆元

3. 原根的应用

   1. 模数为指数的高次剩余问题 $ x^a\equiv b \mod p $

3. 积性函数

1. Dirichlet特征

   1. 有周期

   2. 完全积性

   3. $ f(1)=1 $

2. 积性函数与完全积性函数

3. 常用积性函数

   1. 欧拉函数($\varphi$)：$ \varphi(n) $ 表示1~n中与n互质的数的个数

   2. 莫比乌斯函数($\mu$)：$ \mu(1)=1 $ ，若 $ n(n＞1) $ 含有多重质因数，则 $ μ(n)=0 $ ，否则 $ μ(n)=(-1)^r $ ，$r$表示$n$的质因数个数(与容斥比较像)

   3. 除数函数($ σ $)：一类函数，每个非负整数x都对应一个除数函数$σ x $，$σ x (n)$表示n的因数的x次方之和

4. 欧拉筛筛欧拉函数

5. 欧拉函数的推论

   1	当n>1时，1~n中与n互质的数的和为n*φ(n)/2

6. 欧拉定理

   1	若n,a∈N满足gcd(n,a)=1，则a^φ(n) ≡1(mod n)

7. 扩展欧拉定理

   1 2 3 4

   设a,b,n∈N，若： • gcd(n,a)=1，则a^b ≡a^b mod φ(n) (mod n) • gcd(n,a)≠1，b≤φ(n)，则用快速幂计算 • gcd(n,a)≠1，b>φ(n)，则a^b ≡a^(b mod φ(n))+φ(n) (mod n)

8. 莫比乌斯函数的积性函数

9. 其他积性函数

   1 2 3 4 5 6 7 8

   • 常函数(1)：∀n∈N，1(n)=1 • 单位函数(id)：∀n∈N，id(n)=n • 幂函数(id k )：∀n∈N，id k (n)=n k • 狄利克雷卷积单位函数(ε)：ε(1)=1，∀n>1，ε(n)=0 • 元函数(e)：这是一个由命题映射到N的特殊函数, e[P]=1当且仅当P为真，否则e[P]=0 • 倒数函数(f)：∀n∈N，f(n)=1/n • 值得一提的是，这些函数都是完全积性函数

10. 保留 狄利克雷

11. 两个重要推论

    1. $ \mu \times 1=\varepsilon $

    2. $ \varphi \times 1=id $

12. 莫比乌斯反演定理

    $ f×1=g↔μ×g=f $

13. 四个卷积结论：

    1. $ \varphi \times 1=id $

    2. $ μ \times id=\varphi $

    3. $ μ \times 1=\varepsilon $

    4. $ \varepsilon \times1 =1 $