OIer-Code-Template 这里有我两年OI学习的代码模板干货

                                       ～饼家干货铺

---

一、位运算—数论—组合数学

位运算

1. （归并、树状数组）求逆序对
2. 矩阵快速幂
3. ST算法

欧几里得算法

1. 最大公因数
2. 扩展欧几里得

逆元

1. 逆元
2. 线性求逆元

素数及素数筛

1. 欧拉线性筛
2. 线性筛求欧拉函数
3. 线性筛求约数（个数）和*
4. miller_rabin素数判定*

其他

1. 中国剩余定理*
2. 高斯消元法*

组合数学

1. 卢卡斯定理*

多项式算法

1. FFT
2. NTT

---

二、图论

最短路

1. 最小环

树

1. 树的重心
2. 树的直径
3. lca+树上倍增
4. 最小生成树

tarjan（及其他）算法

无向图

1. 割点（顶）
2. 桥+e-dcc缩点
3. v-dcc缩点
4. 欧拉（回）路

有向图

1. scc+缩点+topo

二分图

1. 二分图判定
2. 二分图最大匹配（匈牙利算法）

网络流

1. 最大流
2. 费用流

---

三、字符串算法

1. 字符串哈希

• 双hash判等
• 子串hash判等

2. KMP算法
3. 最小表示法
4. tire字典树
5. AC自动机
6. 后缀数组*
7. 后缀自动机*
8. manacher算法
9. 回文自动机*

---

四、高级数据结构

1. 树状数组

• 区间加区间和树状数组*

2. 线段树

• 权值线段树*
• 动态开点线段树*

3. 堆

• 对顶堆
• 带删除的堆
• 可并堆(左偏树)*

4. 平衡树*

• treap
• splay
• fhq_treap

5. 可持久化数据结构*

• 主席树

6. hash

• hash判重
• 康托展开

7. LCT

---

五、实用模板

1. 离散化