ACM-ICPC 模板整理.pdf

【核心代码】

目录
1 动态规划 10
1.1 基于位运算的最长公共子序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 决策单调且不要求在线时的糙快猛优化方法 . . . . . . . . . . . . . . . . . . . . . 11
1.3 悬线法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 插头 DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 整数划分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 莫队算法 14
2.1 普通莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 树上莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 树上带修改莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 二维莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 数据结构 19
3.1 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Hash 表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.2 字符串 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.3 矩阵 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 树状数组区间修改区间查询 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 K-D Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4 Link-Cut Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Top Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.6 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6.1 普通 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6.2 缩点 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.7 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.8 替罪羊树实现动态标号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.9 权值线段树中位数查询 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.10 线段树合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.11 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1
ACM-ICPC 模板整理 From Hangzhou Dianzi University
3.12 李超线段树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.13 ST 表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.14 左偏树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.15 带修改区间第 k 小 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.16 Segment Beats! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.17 二维树状数组矩阵修改矩阵求和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.18 并查集按秩合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 树 44
4.1 动态维护树的带权重心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 支持加边的树的重心的维护 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 虚树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4 曼哈顿最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 树链求交 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 图 50
5.1 欧拉回路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.1 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.2 SPFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.3 Astar 求 k 短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.4 稳定 k 短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3 Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1 边双连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 点双连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.3 Dominator Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 强连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 无负权图的最小环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.6 2-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7 完美消除序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.8 最大团 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8.1 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8.2 随机贪心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8.3 独立集最大团计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.9 最大独立集的随机算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.10 差分约束系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.11 点覆盖、独立集、最大团、路径覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.12 匈牙利算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.12.1 二分图字典序最小匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.13 Hall 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2
ACM-ICPC 模板整理 From Hangzhou Dianzi University
5.14 网络流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.14.1 ISAP 求最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.14.2 上下界有源汇网络流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.14.3 费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.14.4 混合图欧拉回路判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.14.5 线性规划转费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.15 最小树形图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.15.1 输出方案 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.15.2 左偏树优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.16 构造双连通图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.17 一般图最大匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.18 图的绝对中心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.19 Hopcroft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.20 KM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.21 强连通竞赛图哈密顿回路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.22 最小割判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.23 二分图匹配判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.23.1 关键点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.23.2 关键边 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.24 动态桥边个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.25 平均数最小环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.26 团和独立集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.27 动态最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6 博弈论 82
6.1 SG 函数的计算方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3 Bash Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4 Nim-k Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.5 Anti-Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.6 Anti-SG Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.7 Staircase Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.8 Lasker’s Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.9 Wythoff Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.10 树上删边游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.11 无向图删边游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.12 翻硬币游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.12.1 每一次只能翻转一枚硬币 . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.12.2 每一次可以翻转一枚或两枚硬币 . . . . . . . . . . . . . . . . . . . . . . . . 84
6.12.3 Twins Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3
ACM-ICPC 模板整理 From Hangzhou Dianzi University
6.12.4 每一次必须翻连续的 n 个硬币 . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.12.5 Ruler Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.13 K 倍动态减法游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.14 Blue-Red Hackenbush . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.15 高维组合游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7 数学 87
7.1 Bell 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2 扩展欧几里得算法解同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.3 同余方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.4 线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.4.1 异或线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.4.2 实数线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.5 原根、指标、离散对数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.5.1 求原根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.5.2 扩展 Baby Step Giant Step . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.6 Catalan 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.7 扩展 Cayley 公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.8 Jacobi’s Four Square Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.9 复数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.10 高斯消元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.10.1 行列式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.10.2 Matrix-Tree 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.11 康托展开 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.12 自适应 Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.13 线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.14 实数线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.15 调和级数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.16 曼哈顿距离的变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.17 拉格朗日乘数法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.18 线性递推逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.19 组合数取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.19.1 Lucas 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.19.2 P 是质数的幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.20 超立方体相关 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.21 平面图欧拉公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.22 线性筛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.23 数论函数变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.23.1 疯狂的前缀和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.24 快速傅里叶变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4
ACM-ICPC 模板整理 From Hangzhou Dianzi University
7.24.1 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.24.2 NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.24.3 多项式求幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.24.4 拉格朗日反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.25 蔡勒公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.26 皮克定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.27 组合数 lcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.28 区间 lcm 的维护 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.29 中国剩余定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.30 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.31 快速沃尔什变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.31.1 K 进制异或卷积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.32 幂和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.33 斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.33.1 第一类斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.33.2 第二类斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.34 各种情况下小球放盒子的方案数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.35 错排公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.36 Prufer 编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.37 二项式反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.38 x
k 的转化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.39 快速计算素数个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.40 素数的幂的和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.41 求不超过 n 的模 P 为每个数的素数个数 . . . . . . . . . . . . . . . . . . . . . . . 107
7.42 Best Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.43 法雷序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.44 分数拟合小数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.45 FFT 模任意质数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.46 拉格朗日四平方和定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.47 Pell 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.48 O(1) 求 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.49 拉格朗日插值法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.50 二次剩余 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.51 一般积性函数求和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.52 第 k 小的期望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.53 固定 k 个点为根的带标号有根树森林计数 . . . . . . . . . . . . . . . . . . . . . . 117
7.54 斯特林近似公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.55 伯努利数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.56 类欧几里得算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.57 置换开根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5
ACM-ICPC 模板整理 From Hangzhou Dianzi University
7.58 反欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.59 毕达哥拉斯三元组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.60 Stern-Brocot Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.61 Berlekamp-Massey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.62 ax by c=0 的整数解个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.63 切比雪夫多项式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.64 斜率绝对值为 1 的折线计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.65 等比矩阵求和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.66 等价类容斥 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.67 掷硬币 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.67.1 二人游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.67.2 多人游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.67.3 作为子串出现的概率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.68 泰勒展开 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8 字符串匹配 129
8.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.2 最小表示法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.3 AC 自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.4 回文串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.4.1 Manacher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.4.2 Palindromic Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.6 后缀树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.7 后缀自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.8 后缀自动机 - Claris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.9 后缀自动机统计子串出现次数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.10 后缀平衡树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.11 Basic Factor Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.12 可持久化 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.13 扩展 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.14 循环最长公共子序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.15 生成 Lyndon Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.16 ALCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
8.17 Shift And . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9 随机化 146
9.1 Pollard Rho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.2 最小圆覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
9.3 最小球覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6
ACM-ICPC 模板整理 From Hangzhou Dianzi University
10 计算几何 149
10.1 半平面交 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.2 最小矩形覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
10.3 三维凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10.4 球缺 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.5 2D 计算几何模板大全 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.6 曼哈顿凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
10.7 圆的面积并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
10.8 平面图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
10.8.1 直线分割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.8.2 线段分割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
10.9 Descartes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.10动态凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.11四面体内切球公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
10.12长方体表面两点距离 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
10.133D 计算几何基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
10.14经纬度求球面最短距离 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10.15三维旋转操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10.16DP 凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10.17凸包切线 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
10.18欧几里得最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.19直线与凸包交点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
10.20平面最近点对 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
10.21三维投影平面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
11 黑科技与杂项 185
11.1 开栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.1.1 32 位 Win 下 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.1.2 64 位 Linux 下：(对 main() 中的汇编语句做修改) . . . . . . . . . . . . . 185
11.1.3 简化版本 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.2 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.2.1 普通 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.2.2 文艺 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
11.2.3 二逼 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.2.4 fread 判 EOF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.3 位运算及其运用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.3.1 枚举子集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.3.2 求 1 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.3.3 求前缀 0 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.3.4 求后缀 0 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7
ACM-ICPC 模板整理 From Hangzhou Dianzi University
11.4 石子合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.5 最小乘积生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.6 特征多项式加速线性递推 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.7 三元环的枚举 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.8 所有区间 gcd 的预处理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.9 无向图最小割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.9.1 堆优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.10分割回文串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.112-SAT 计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.12高精度计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
11.13高精度计算 - Claris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
11.14Rope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
11.14.1示例 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
11.14.2示例 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
11.15pb_ds 的红黑树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
12 Java 207
12.1 输入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.1.1 声明一个输入对象 cin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.1.2 输入一个 int 值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.1.3 输入一个大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.1.4 EOF 结束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.2 输出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.3 大数类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.3.1 赋值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.3.2 比较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.3 基本运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.4 BigDecimal 的格式控制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.5 创建 BigDecimal 对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.3.6 对 bigNumber 的值乘以 1000，结果赋予 bigResult . . . . . . . . . . . . . 209
12.3.7 BigInteger 的进制转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.4 小数四舍五入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.5 高精度小数 A B，输出最简结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.6 斐波那契数列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.7 两个高精度浮点数比较是否相等 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.8 高效的输入类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
12.9 输出外挂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8
ACM-ICPC 模板整理 From Hangzhou Dianzi University
13 战术研究 212
13.1 注意点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
13.2 打表找规律方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212