简介：《ACM基础算法模板2》是一份面向算法竞赛初学者和ACM选手的便携模板集，覆盖快速读入、高精度四则运算、快速幂、组合数与排列数、质数判定、分解质因数、欧拉筛等常考基础模块，并附有GCD/LCM与整数二分查找模板，适合日常刷题和赛前速查，对刚接触算法竞赛的读者尤为友好。包内共1个PDF文件，压缩包仅513KB，体积小巧，便于按目录快速定位、对照抄写或打印携带。已有225人学习浏览，适合需要系统夯实数论与高精度基础的读者。文件中每个模板都给出可直接调用的C++函数实现，并对关键边界做了注释：例如快读兼容负数、高精度除法的余数通过引用返回、欧拉筛利用最小质因子退出循环等，能帮助理解原理而非死记代码。高精度系列突出进位/借位处理，数学部分给出模运算与逆元预处理写法，可作为长期留存的备赛笔记，整体实用性强。
1. 为什么每位 ACM 选手都在持续维护一份《ACM基础算法模板2》
一场五小时的四小时提交队列里，前六十分钟大家都能写出最短路和最小生成树，真正拉开差距的是谁能在最后一百分钟把后缀自动机、费用流这类高难度模板从编辑器里调出来直接改。所谓《ACM基础算法模板2》，并不是给你一份复制粘贴即 AC 的「葵花宝典」，而是帮助你沉淀一套有分类、有参数、有边界条件、可快速改写的数据结构与算法的代码骨架。它解决的核心问题只有一个：把「从零写一遍」变成「改一改参数跑通」，把赛场上最贵的思考时间留给题目本身。
这套模板适合正在准备区域赛或校赛的选手，也适合想系统梳理常见算法套路、并在笔试或面试中快速验证思路的开发者。它的价值不在于代码本身有多漂亮，而在于你能否在压力下准确调用，并且知道每一行背后为什么这么写。如果你见过那些 .cpp 文件动辄两千行、命名乱到查都查不到的选手，你就明白模板工程化和「能用」之间差着一条血泪经验的鸿沟。接下来我会按我的实际维护思路，把这套体系打散重讲，从组织方式、核心模块、参数边界到避坑点逐一拆开。
2. 模板工程化的第一步：分类骨架、命名规范与代码复用策略
2.1 先设计目录骨架：按算法类别分文件，而不是按题号存代码
ACM 基础算法模板的组织方式决定你赛场上找代码的速度。常见做法是把代码按类别拆成独立的 .h 或 .cpp 片段，放到同一个目录里集中管理。我一般用的目录骨架是：
acm-templates/ ├── math/ # 数论、组合、线性基、FFT ├── graph/ # 最短路、网络流、匹配、树相关 ├── string/ # KMP、AC 自动机、后缀数组、Manacher ├──>// tools/FastIO.h 片段 #pragma once #include <bits/stdc++.h> using namespace std; struct FastScanner { static const int BUFSIZE = 1 << 20; int idx, size; char buf[BUFSIZE]; FastScanner(): idx(0), size(0) {} inline char getChar() { if (idx >= size) { size = fread(buf, 1, BUFSIZE, stdin); idx = 0; if (size == 0) return '\0'; } return buf[idx++]; } template <typename T> bool readInt(T &out) { char c; T sign = 1; T num = 0; c = getChar(); if (c == '\0') return false; while (c != '-' && (c < '0' || c > '9')) { c = getChar(); if (c == '\0') return false; } if (c == '-') { sign = -1; c = getChar(); } for (; c >= '0' && c <= '9'; c = getChar()) num = num * 10 + (c - '0'); out = num * sign; return true; } };这段代码的核心思路是用自定义缓冲区替代标准cin的逐字符解析，减少 I/O 库内部开销。参数说明：BUFSIZE一般取 1<<20 即 1MB，太大浪费内存，太小会增加fread调用次数；readInt返回false表示读到文件末尾，因此在多组数据场景里你可以用while (fs.readInt(n))作为循环条件。注意T sign使用模板类型而不是long long，是为了保持整数类型一致，避免赋值时产生符号位扩展的隐式转换问题。
3. 图论与数据结构模板的实战写法：从最短路到并查集
3.1 用链式前向星封装图结构：数组化存储保证内存连续
图论模板的地基是图存储方式。我们常说邻接表用vector<int> adj[N]简洁易读，但 ACM 赛场上更常见的做法是链式前向星，因为它在处理多组测试数据时不需要频繁clear()，只需要重置head数组和cnt即可，并且内存连续对缓存友好。
// graph/LinkedForwardStar.h const int MAXN = 100005; const int MAXM = 200005; struct Edge { int to, next, weight; } edges[MAXM]; int head[MAXN], cnt; void initGraph(int n) { cnt = 0; memset(head, -1, sizeof(int) * (n + 1)); } void addEdge(int u, int v, int w) { edges[cnt].to = v; edges[cnt].weight = w; edges[cnt].next = head[u]; head[u] = cnt++; } void addUndirectedEdge(int u, int v, int w) { addEdge(u, v, w); addEdge(v, u, w); }逻辑说明：head[u]存储的是从 u 出发的第一条边的下标，next指向下一条边。每次新增边都插入链表的头部，所以遍历顺序和输入顺序相反，但这不影响算法正确性。初始化时把head前n+1个位置置为 -1，避免对整个数组做memset，当题目n很小但数组很大时能省下不少时间。参数注意：MAXM对于无向边要开两倍大小，这是最容易被新手忽略的前提。
3.2 Dijkstra 堆优化模板：INF 的取值与模板参数传递
在链式前向星之上写堆优化的 Dijkstra 是区域赛最常用的路径模板。代码中使用priority_queue维护当前距离最小的节点，配合vis数组标记是否已确定最短路。
// graph/Dijkstra.h #include <queue> #include <cstring> struct Status { int u; long long dist; bool operator<(const Status &other) const { return dist > other.dist; // 小顶堆 } }; void dijkstra(int start, int n, long long dist[], int pre[]) { const long long INF = 0x3f3f3f3f3f3f3f3fLL; for (int i = 1; i <= n; i++) { dist[i] = INF; pre[i] = -1; } priority_queue<Status> pq; dist[start] = 0; pq.push({start, 0}); while (!pq.empty()) { Status top = pq.top(); pq.pop(); if (top.dist != dist[top.u]) continue; // 跳过过期状态 for (int e = head[top.u]; e != -1; e = edges[e].next) { int v = edges[e].to; long long nd = top.dist + edges[e].weight; if (nd < dist[v]) { dist[v] = nd; pre[v] = top.u; pq.push({v, nd}); } } } }两个细节值得说明。第一，INF = 0x3f3f3f3f3f3f3f3fLL而不是INT_MAX，是因为dist要做加法运算，用INT_MAX加上一个正边权会溢出成负数，进而被错误地当作更短路径。0x3f3f3f3f 这个十六进制的每字节都是 0x3f，两个这样的值相加仍然小于 64 位有符号整数上限，这是竞赛圈最常用的「安全无限大」。第二，pre数组用于路径回溯，不需要时可以传nullptr，但保留它能在你怀疑答案错误时快速打印路径做核对。
3.3 并查集的路径压缩与按秩合并：两个优化缺一不可
并查集看起来简单，但模板里同时写路径压缩和按秩合并能保证find操作接近常数级别复杂度。单独使用路径压缩时，find的均摊复杂度已经接近常数，但如果遇到极端构建的退化树，递归深度仍可能让栈溢出；按秩合并则进一步控制树高。
//>//>// string/KMP.h vector<int> buildNext(const string &pattern) { int m = (int)pattern.size(); vector<int> next(m + 1, 0); for (int i = 1, j = 0; i < m; i++) { while (j > 0 && pattern[i] != pattern[j]) j = next[j]; if (pattern[i] == pattern[j]) j++; next[i + 1] = j; } return next; } vector<int> kmpSearch(const string &text, const string &pattern) { vector<int> next = buildNext(pattern); vector<int> matches; int m = (int)pattern.size(); for (int i = 0, j = 0; i < (int)text.size(); i++) { while (j > 0 && text[i] != pattern[j]) j = next[j]; if (text[i] == pattern[j]) j++; if (j == m) { matches.push_back(i - m + 1); j = next[j]; } } return matches; }这套模板采用的是next[i+1] = j的写法，next[i]代表模式串前 i 个字符的最长相等前后缀长度。失配时j = next[j]的含义是：当前已匹配到模式串第 j 个字符（0 基），前 j 个已成功匹配，那就用这前 j 个字符的最长前后缀长度作为下一次继续比对的位置。参数说明：当j == m时表示匹配成功，记录起始位置i - m + 1，然后把j置为next[m]，相当于复用已匹配前缀中的后缀部分，继续寻找下一个重叠匹配。
4.2 快速幂与模运算：小心负数取模和乘法溢出
数论模板里最基础也最常用的是快速幂，应用范围覆盖模逆元计算、矩阵快速幂前置步骤、指数取模等场景。这里需要注意 C++ 的取模运算对负数并非数学意义上的取模，因此模板里要单独处理负数情况。
// math/QuickPow.h long long quickPow(long long base, long long exp, long long mod) { long long res = 1 % mod; base %= mod; if (base < 0) base += mod; // 处理负数底数 while (exp > 0) { if (exp & 1) { res = (res * base) % mod; } base = (base * base) % mod; exp >>= 1; } return res; } long long modAdd(long long a, long long b, long long mod) { a %= mod; b %= mod; if (a < 0) a += mod; if (b < 0) b += mod; return (a + b) % mod; }逻辑说明：快速幂把指数拆成二进制位，底数每移位一次就自乘一次，只有在当前二进制位为 1 时才把累积结果乘上底数的当前幂。这样做的时间复杂度是 O(log exp)。参数注意：mod为 1 时，1 % mod等于 0，避免返回 1 导致错误；base ^ 2在long long范围内相乘，如果mod接近 1e18，需要改用快速乘（将乘法拆位相加）来避免溢出，这是模板里最容易被忽略的隐藏风险。
4.3 Z 算法与 Manacher：什么时候值得放进进阶模板
如果你的《ACM基础算法模板2》定位是区域赛冲奖级别，那么字符串章节至少还要加入 Z 算法、Manacher 和 AC 自动机。Z 算法的核心思想是维护一个[l, r]区间，记录已匹配的最靠右的相同前缀区间。它的实现比 KMP 更短且更直观，但使用率低于 KMP，所以我会将它放在同一文件中作为备选函数。
// string/ZAlgorithm.h vector<int> zFunction(const string &s) { int n = (int)s.size(); vector<int> z(n); int l = 0, r = 0; for (int i = 1; i < n; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z; }z[i]表示从 i 开始的子串与整个字符串s的最长公共前缀长度。注意当i <= r时可以直接从已经计算过的z[i-l]继承初始值，但不能超过r - i + 1这个区间边界。该模板用于「在一个文本串中查找模式串的所有出现位置」时，常用做法是把模式串和文本串用分隔符合并成一个字符串，再对合并后的字符串求 Z 数组，识别出 Z 值等于模式串长度的位置。
5. 避坑排查手册：模板复用时最常翻车的五个环节
5.1 现象：多组数据之间状态残留导致答案诡异地递增或错乱
每次使用模板前忘记重置全局数组是 ACM 赛场上最常见的犯傻方式。链式前向星的cnt没有归零，Dijkstra 的dist数组只初始化了前 n 个，可上一次数据 n 更大时留下尾部脏数据，这些并不会直接编译报错，而是让算法结果变得完全不可预测。解决方法是统一封装一个reset函数，并在每组数据输入后第一时间调用，养成肌肉记忆：先读 n，再 reset，再读边。
5.2 现象：堆优化的 Dijkstra 在使用visited标记后偶尔 WA
visited数组在 Dijkstra 中的作用本应是防止重复处理节点，但是在优先队列中，一个节点可能被多次松弛后 push 进去。正确写法是使用if (top.dist != dist[top.u]) continue;而不是在 pop 时检查visited。原因是当节点被更长的路径再次更新时，visited已经被置为 true，你会跳过所有后续的松弛机会。这类 bug 非常隐蔽，因为小数据跑几次都能过，一旦数据量上来就随机翻车。
5.3 现象：线段树的懒惰标记只在更新时下推，查询时忘记推导致区间查询错误
懒标记设计的要点是「用到哪个节点就推哪个节点」。很多人写的update函数有pushDown调用，但query函数里却漏掉了，导致上层节点保留了未下推的 lazy 值，又直接返回了过时的sum。排查方式：写一个小型暴力对拍程序，随机生成区间加和区间求和操作，比对线段树结果和朴素数组的结果是否一致。此类问题一旦复现，你的模板会在压力测试下暴露原型。
5.4 现象：KMP 匹配在模式串最后一个字符失配时越界下标
部分选手把 next 数组实现为长度 m 而不是 m+1，在j = next[j]时如果j恰好等于 m，下一次访问pattern[j]就会越界。因此在匹配循环的while (j > 0 && text[i] != pattern[j])之前，必须先保证j < m，或者直接使用 m+1 长度的 next 数组并让next[m]有意义。这是字符串模板的小坑，老选手通常靠记忆规避，但建议在文档注释里写清楚next的下标约定。
5.5 现象：模运算结果为负数导致判题返回 WA
C++ 的%运算符对负数返回负数，比如(-5) % 3在数学上期望是 1，但 C++ 返回 -2。如果你在计算组合数模 p、逆元等场景没有做修正，就会得到完全错误的结果。通用修正是result = (result % mod + mod) % mod。这个修正不是可有可无的，需要写进所有数学模板的公共工具函数里。
6. 让模板成为肌肉记忆：压力测试与赛前自检的实用技巧
模板写完之后并不能直接上赛场，你需要通过若干轮「模板题」检验每个算法片段是否在紧张环境下仍然能快速适配。我的习惯是：每个月从在线评测系统的题目集里挑出十道模板型题目，覆盖最短路径、并查集、线段树、KMP、快速幂和维护最值这几类高频依赖，每道题限定二十分钟内完成调通。这不仅仅是为了验证代码正确，更是为了强迫自己记住模板的关键改动点：比如 Dijkstra 的模板里pre数组是否需要打开，线段树的lazy是否需要long long，KMP 的 next 长度是 m 还是 m+1。
第二个技巧是为每个模板文件编写「改动清单」注释。在文件头部注释里写清楚这个算法的常见变体，比如「Dijkstra 改边权为负时要用 SPFA，不可用本模板」「线段树区间取最大值时要同时维护 min 和 max 两个值」「KMP 若匹配模式串本身为前缀，需要在循环末尾检查 j 是否为 0」。这些注释的价值在于，当你半年后重新打开这份模板时，能迅速回忆起当初踩过的坑，而不是重新陷入漫长的代码考古。
最后值得一提的是模板的多版本管理。我不建议把每个算法的旧写法删掉重写，而应该用注释保留一个基础版本和一个优化版本。比如并查集可以同时保留递归 find 和循环 find 两种实现，递归版代码短但深度有风险，循环版稍长但更稳。赛后复盘时看到哪些模板被高频修改，就定期把那些常用改法固化到主模板里。我自己曾经在区域赛模拟赛上因为快速幂模板没有处理 mod = 1 的边界而丢掉一整道题的分，从此以后每份模板都带上了边界测试注释。希望帮到你。
本文还有配套的精品资源，点击获取
