ACM 常用算法模板
kuangbin
http://www.cnblogs.com/kuangbin/
Email:kuangbin2009@126.com
Last build at July 8, 2018
ACM Template of kuangbin
Contents
1 字符串处理 5
1.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 e-KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Manacher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 AC 自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 DC3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 后缀自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.1 基本函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.2 例题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 字符串 hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 数学 25
2.1 素数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 素数筛选（判断 <MAXN 的数是否素数） . . . . . . . . . . . . . . . . 25
2.1.2 素数筛选（筛选出小于等于 MAXN 的素数） . . . . . . . . . . . . . . . 25
2.1.3 大区间素数筛选（POJ 2689） . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 素数筛选和合数分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 扩展欧几里得算法（求 ax+by=gcd 的解以及逆元） . . . . . . . . . . . . . . . 27
2.4 求逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 扩展欧几里德法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 简洁写法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 利用欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 模线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.1 分解质因素求欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.2 筛法欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.3 求单个数的欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.4 线性筛（同时得到欧拉函数和素数表） . . . . . . . . . . . . . . . . . . 32
2.8 高斯消元（浮点数） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.9 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.10 高斯消元法求方程组的解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.10.1 一类开关问题，对 2 取模的 01 方程组 . . . . . . . . . . . . . . . . . . . 37
2.10.2 解同余方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.11 整数拆分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.12 求 A
B
的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.13.1 莫比乌斯函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.13.2 例题：BZOJ2301 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.14 Baby-Step Giant-Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.15 自适应 simpson 积分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.16 斐波那契数列取模循环节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.17 原根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.18 快速数论变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.19.1 Polya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
kuangbin 1
ACM Template of kuangbin
3 数据结构 56
3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.1 一维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.2 二维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1 点权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.2 边权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4 伸展树（splay tree） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.1 例题：HDU1890 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.2 例题：HDU3726 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5 动态树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1 SPOJQTREE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.2 SPOJQTREE2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.3 SPOJQTREE4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.5.4 SPOJQTREE5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.5.5 SPOJQTREE6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5.6 SPOJQTREE7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.5.7 HDU4010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6 主席树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.1 查询区间多少个不同的数 . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.2 静态区间第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6.3 树上路径点权第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.6.4 动态第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.8 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.1 HDU4347 K 近邻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.2 CF44G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.8.3 HDU4742 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.9 替罪羊树 (ScapeGoat Tree) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.9.1 CF455D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.10 动态 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.11 树套树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.11.1 替罪羊树套 splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4 图论 130
4.1 最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.1 Dijkstra 单源最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.2 Dijkstra 算法 + 堆优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.3 单源最短路 bellman_ford 算法 . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.4 单源最短路 SPFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.2 最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.1 Prim 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.2 Kruskal 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3 次小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.4 有向图的强连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.1 Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.2 Kosaraju . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5 图的割点、桥和双连通分支的基本概念 . . . . . . . . . . . . . . . . . . . . . . . 138
4.6 割点与桥 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.6.1 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
kuangbin 2
ACM Template of kuangbin
4.6.2 调用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.7 边双连通分支 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.8 点双连通分支 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.9 最小树形图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.10 二分图匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.10.1 邻接矩阵（匈牙利算法） . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.10.2 邻接表（匈牙利算法） . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.10.3 Hopcroft-Karp 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.11 二分图多重匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.12 二分图最大权匹配（KM 算法） . . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.13 一般图匹配带花树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.14 一般图最大加权匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.15 生成树计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.16 最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.16.1 SAP 邻接矩阵形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.16.2 SAP 邻接矩阵形式 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.16.3 ISAP 邻接表形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.16.4 ISAP+bfs 初始化 + 栈优化 . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.16.5 dinic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.16.6 最大流判断多解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.17 最小费用最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.17.1 SPFA 版费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.17.2 zkw 费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.18 2-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.18.1 染色法（可以得到字典序最小的解） . . . . . . . . . . . . . . . . . . . . 172
4.18.2 强连通缩点法（拓扑排序只能得到任意解） . . . . . . . . . . . . . . . . 173
4.19 曼哈顿最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.20 LCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.20.1 dfs+ST 在线算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.20.2 离线 Tarjan 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.20.3 LCA 倍增法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
4.21 欧拉路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.21.1 有向图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.21.2 无向图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4.21.3 混合图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.22 树分治 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.22.1 点分治 -HDU5016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.22.2 * 点分治 -HDU4918 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.22.3 链分治 -HDU5039 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5 搜索 205
5.1 Dancing Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.1.1 精确覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.1.2 可重复覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.2 八数码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
5.2.1 HDU1043 反向搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
6 动态规划 212
6.1 最长上升子序列 O(nlogn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.2 背包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.3 插头 DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
kuangbin 3
