简介一份面向ACM竞赛入门与进阶选手的算法模板速查手册聚焦数论与基础数据结构方向的高频必备知识。文档以C实现为线索先后讲解宏定义、快速读写、GCD/LCM、扩展欧几里得、快速幂与快速乘、组合数计算以及Lucas定理每个模板均附有可复用代码和关键点说明其中gcd采用辗转相除法exgcd可同时求得一组贝祖等式解。例如快读函数通过getchar与位运算优化整数输入输出Lucas定理将大组合数取模递归拆分为小规模计算便于直接套用于比赛与练习。资源为单个PDF文件压缩包整体仅53KB文档体量轻巧目录结构清晰适合赛前速览或离线查阅。当前已有531人学习下载对于希望系统整理常用赛题模板的ACM选手来说是一份轻量而实用的基础资料。1. ACM 基础模板赛前抄这一份少踩一半的坑想象你在比赛只剩三分钟时拿到正确思路却因为cin读十万条边超时整题 TLE 收场或者组合数C(1000, 500)算到一半溢出成负数输出一长串莫名其妙的数字。这份 ACM 基础模板就是为这种时刻准备的——宏定义、快读快写、快速幂、gcd、组合数与 Lucas 定理全部封装成能直接抄走的 C 代码块。它不是神秘的黑匣子而是竞赛里高频操作的速查手册适合用 C 打 ACM、蓝桥杯和力扣周赛的选手。读完后你会知道每个函数为什么这么写参数怎么调以及哪些边界条件最容易坑人。2. 宏定义与快读快写把 IO 速度从「够用」拉到「不卡」2.1 FAST 宏与类型重定义先看懂这几行再抄先看模板开头的这段#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); #define X first #define Y second typedef long long LL; typedef unsigned long long ULL; typedef pairint, int PII; const int INF 0x3f3f3f3f; // 约为10.6亿加边权不溢出 const int MOD 1e9 7; // 常用素数模数这段共 8 行从宏到 typedef 再到 const每一类都有自己的用途。先说FAST。ios::sync_with_stdio(false)关闭了iostream和 C 标准库 stdio 之间的同步锁。默认状态下cin/cout会与scanf/printf共享底层缓冲以保证混用不乱序但同步带来的开销极大——每读一个字符都要检查两侧状态。关掉同步后cin/cout走自己的通路速度可以逼近scanf。代价是同一份代码里不能混用cin和scanf否则读取顺序完全不可控。cin.tie(0)解决另一个问题默认cin会和cout绑定每次cin读入前都先flush一次cout缓冲区。这个刷新操作非常昂贵尤其在反复读写的循环里。tie(0)解除绑定让两边各干各的。这两行组合在一起就是竞赛里通用的「让 cin 变快」操作。X和Y是pair.first/pair.second的简写。比赛里用pair存坐标、存堆节点时a.X比a.first少打六个字符手速就是在这种细节里攒出来的。LL、ULL、PII同理属于每场必用的类型缩写比手写long long省事得多。重点说INF。很多新手写const int INF 0x7fffffff也就是INT_MAX。这玩意儿碰上dis[v] dis[u] w这种判断时INT_MAX w直接溢出成负数条件永远为假最短路跑出来全是 INF。0x3f3f3f3f约 10.6 亿距离 int 上限还有约 10 亿空间加一个常见边权不会溢出。这个细节属于一次踩坑终身受益。MOD 1e9 7是竞赛圈最常用的模数够大、能容纳常见运算中间值而且是素数后面组合数求逆元要依赖这个性质。提示宏定义X和Y会降低代码可读性。如果是团队协作建议只在关键位置用别满篇a.X到底。2.2 快读 read() 与快写 write()逐字符搬运的艺术inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) { f -1; c getchar(); } else c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; } inline void write(int x) { if (x 0) { putchar(-); x -x; } if (x 9) write(x / 10); putchar(x % 10 0); }read()的思路是绕过scanf的格式解析直接用getchar()逐字符读整数。第一个 while 循环跳过所有非数字字符碰到-就把符号记到f上。跳过空白这段很重要ACM 题的输入通常夹杂大量空格和换行scanf(%d)内部也是这么处理的只是它要做的事更多速度就慢了。第二个 while 循环做数字拼接每读到一个数字字符x x * 10 c - 0。以输入 925 为例循环内依次得到0*1099、9*10292、92*105925最后乘上符号。字符转数字用c - 0因为 ASCII 中 0 是 48减完正好得到 0 到 9 的整数值。write()是递归输出x 9说明有多位先递归输出x / 10把高位全部打出最后putchar(x % 10 0)输出当前位。write(123)的过程是123 → 12 → 1再从内向外putchar(1)、2、3。负数先putchar(-)再取绝对值输出递归深度最多 10 层不会爆栈。这里有个容易被忽略的细节read()和write()都标了inline这提示编译器在调用处直接展开函数体省去函数调用的栈操作。IO 函数在百万次循环里被调用极频繁一次展开省一点累积起来就是几秒的差距。编译器一般会尊重这个建议但写上是稳妥习惯。同时也已经有明摆着的坑第一read()不支持浮点数、字符串它不是万能输入函数第二getchar()读到 EOF 返回 -1此时c 0成立第一个 while 会死循环所以模板里的read()不能用来读「未知个数的整数」——避坑章节会给改造版。2.3 使用边界多少输入量才值得用快读快读快写的收益跟输入规模强相关。我个人的判断标准是输入规模推荐方式原因1 万以下cin FAST快读优化不明显反而增加代码量10 万以上scanf 或快读cin 的同步开销开始拖后腿100 万级快读快写纯字符搬运能抢回好几秒注意快读只解决整数。如果题目输入里有小数、字符串、混合格式快读就派不上用场。比如read()遇到小数点会把它当非数字跳过读出一个不带小数的错误整数。此时用scanf或cin别硬上。还有一个比赛里常见的混用场景read()读整数、printf输出它们互不干扰。但如果你混用cin和scanf就必须关掉FAST宏否则两个缓冲区状态不同步数据顺序会乱。这个约束是这套模板最容易忽视的点。3. 数论基础四件套gcd、exgcd、快速幂、快速乘3.1 辗转相除法 gcd 与 lcm递归终止条件不能错int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); }gcd 实现用的是辗转相除法核心性质是gcd(a, b) gcd(b, a % b)。每次递归把(a, b)换成(b, a % b)问题规模以对数级别缩小直到b 0时a就是结果。最坏情况出现在斐波那契数列相邻两项比如gcd(55, 34)要递归 8 层但这已经是对数复杂度比赛里不会成为瓶颈。lcm 理论上等于a * b / gcd(a, b)但a * b有隐患。当a和b都接近 2e9 时乘积溢出 int结果就错了。建议改成a / gcd(a, b) * b先除后乘把中间结果控制在 int 范围内。如果你的数据是long long也建议保持这个顺序防止乘积越过 9e18。3.2 扩展欧几里得 exgcd从求 gcd 到求逆元int exgcd(int a, int b, int x, int y) { if (b 0) { x 1; y 0; return a; } int ans exgcd(b, a % b, x, y); int temp x; x y; y temp - a / b * y; return ans; }exgcd 在求 gcd 的同时能解出贝祖等式ax by gcd(a, b)的一组整数解(x, y)。这对组合数的模逆元计算很有用因为当a和p互质时exgcd(a, p, x, y)得到的x恰好满足ax ≡ 1 (mod p)也就是「a 在模 p 下的逆元」。递归回溯时的变量交换我重新推导一遍。假设下一层已经求出了exgcd(b, a % b, x, y)的解(x, y)它满足b*x (a%b)*y gcd。令t a / ba%b a - b*t代入得b*x (a - b*t)*y a*y b*(x - t*y)。对比目标式a*x b*y gcd于是本层解为x yy x - t*y。这就是代码里temp x; x y; y temp - a/b*y;的来源。这个函数有两个现实用途一是求单个模逆元二是解决形如ax by c的丢番图方程。虽然快速幂也能求逆元但quickMi要求模数是素数而 exgcd 只要gcd(a, p) 1就能用适用范围更宽。3.3 快速幂 quickMi 与快速乘 quickMul二进制拆分的双胞胎LL quickMi(LL a, LL b, LL p) { LL res 1; while (b) { if (b 1) res res * a % p; a a * a % p; b 1; } return res % p; } LL quickMul(LL a, LL b, LL p) { LL res 0; while (b) { if (b 1) res (res a) % p; a a * 2 % p; b 1; } return res; }快速幂的原理是把指数 b 做二进制拆分b 13对应二进制1101于是a^13 a^8 * a^4 * a^1。循环每轮把a平方代表当前位的权重if (b 1)判断当前位是否为 1是就把res乘上这一项b 1右移一位。复杂度从 O(b) 降到 O(log b)指数是 long long 时最多 63 轮。快速乘的思路和快速幂同构只是把乘法转成加法a * b中 b 的每个二进制位为 1 时把当前a累加进res每轮a翻倍加法后立刻取模。它把一次大数乘法拆成约 63 次加法取模适合p接近 1e18、a*a会溢出 long long 的场景。普通1e97模数下用不上但和快速幂配套遇到高精度取模题不用临时造轮子。有个细节注意quickMi里res * a和a * a在 p 较小时没问题p 接近 1e18 时必须走quickMul否则乘法越界后取模结果完全错误。3.4 复杂度与适用场景对照函数复杂度典型场景隐患gcdO(log)求最大公约数无lcmO(log)求最小公倍数a*b 溢出exgcdO(log)求逆元 / 解二元一次方程回溯逻辑需理解quickMiO(log)大指数取模 / 逆元a*a 溢出quickMulO(log)大数乘法取模加法稍慢实际竞赛里gcd 和快速幂是最高频的两个lcm 记得改成先除后乘exgcd 平时不太出现但要在求逆元的场景里知道它能救场。快速乘属于替补队员遇到 p 很大的取模题才需要。这套函数能覆盖九成以上的基础数论操作。4. 组合数与 Lucas 定理大数取模该怎么拆4.1 组合数 C(a,b,p)为什么用费马小定理求逆元LL C(LL a, LL b, LL p) { LL res 1; for (int i 1, j a; i b; i, j--) res res * j % p * quickMi(i, p - 2, p) % p; return res; }组合数C(a, b) a! / (b! * (a-b)!)在模 p 意义下不能直接做除法因为分数取模不等于分子取模除以分母取模。正确做法是把分母转成逆元再乘。由于 p 是素数费马小定理给出i^(p-1) ≡ 1 (mod p)两边同除 i 得到i^(p-2) ≡ i^(-1) (mod p)所以quickMi(i, p-2, p)就是 i 的逆元。循环里res * j % p * quickMi(i, p-2, p) % p做的就是「乘上一项分子再乘上对应分母的逆元」。j从a递减到a-b1i从 1 递增到 b正好凑出 b! 的分母部分。返回结果就是C(a, b) mod p。这个实现的复杂度是 O(b)瓶颈在循环次数。当 b 较小、a 较大时它比预处理阶乘的版本省内存不需要 O(a) 预处理。但如果 b 接近 a/2 且 a 有 1e6 级别循环 50 万次就有些压力可以用对称性优化C(a, b) C(a, a-b)取较小的 b 来循环。另一种常见做法是预处理阶乘和逆元数组。当 a 的范围固定、查询次数多时O(a) 预处理加 O(1) 查询更划算。但这个 C() 模板适合 a 很大、查询次数少的场景两者各有适用边界。如果你要处理多组 C(a,b,p)建议改成预处理。4.2 Lucas 定理递归把大组合数拆小LL lucas(LL a, LL b, LL p) { if (a p b p) return C(a, b, p); return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; }Lucas 定理讲的是C(a, b) % p C(a%p, b%p) * C(a/p, b/p) % p其中 p 必须是素数。模板实现很直白如果 a 和 b 都小于 p直接调组合数函数否则拆成C(a%p, b%p)再乘递归的lucas(a/p, b/p)。典型场景是 a、b 达到 1e18p 只有 1e5 或 1e6。直接循环 b 次不现实而 Lucas 每层递归把规模缩小 p 倍总递归层数约 log_p(a)每层调一次C(a%p, b%p)循环长度不超过 p。整体复杂度约O(p * log_p(a))在 p 为 1e6、a 为 1e18 时约 6 轮百万次循环千万级运算完全可接受。有个使用前提容易被忽略p 必须是素数。C()里的逆元依赖费马小定理p 是合数时quickMi(i, p-2, p)不是合法逆元结果会偏。比赛题目一般会明确告知 p 是素数但审题时不能默认。4.3 整套组合数调用示例int main() { FAST; printf(C(10, 3) mod 1e97 %lld\n, lucas(10, 3, 1000000007)); printf(C(1e18, 500000) mod 10009 %lld\n, lucas(1000000000000000000LL, 500000LL, 10009LL)); return 0; }第一行验证小数据手算C(10,3)120能与输出对照。第二行把 Lucas 推到极限a 是 1e18p 是 10009。p 远小于 a所以先进入递归分支把 a 逐层缩小最终在几万次组合数循环里完成计算。如果直接调用 C()b 是 50 万次循环虽然也能跑但 a 是 1e18 时组合数本身已远超整数范围必须靠 Lucas 拆开。注意这里用了FAST宏又用printf两者可以共存因为FAST只影响cin/coutprintf走独立通道。如果混用cin和printf必须关掉FAST或统一cin/cout。这套模板默认 IO 是混用的快读 printf这个使用习惯要记牢。5. ACM 模板避坑指南五条真实踩坑记录模板抄下来只是第一步真正让你在赛场上栽跟头的往往不是算法思路而是隐藏在代码角落里的边界条件。下面五条是我和身边队友真实踩过的坑按频率排序。5.1 万能头文件在本地编译器报错现象把#include bits/stdc.h贴到 Visual Studio 或老版本 GCC编译直接报 no such file。原因bits/stdc.h是 GCC 的扩展预编译头不是 C 标准库内容。MSVC 编译器不包含这个文件部分比赛机 GCC 版本过旧也可能缺失。解决本地调试时手动展开成标准头文件列表iostream、cstring、algorithm、string、vector、queue、stack、set、map、numeric、cmath按需列出。交题时再换回或者全程用标准头文件更稳。5.2 快读读到 EOF 会卡死现象用while (read())读入未知个数的整数程序卡在输入阶段跑不完。原因getchar()在文件末尾返回EOF-1c 0成立read()的第一个 while 永远跳不出来读入就卡死了。解决改造read()识别 EOF 并返回标记inline int read() { int x 0, f 1; char c getchar(); while (c ! - (c 0 || c 9)) { if (c EOF) return EOF; c getchar(); } if (c -) { f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }主调处写while ((x read()) ! -1)注意赋值运算符优先级低于比较必须加括号否则会变成x (read() ! -1)结果完全不对。这里只要题目保证输入为正整数用 -1 作 EOF 标记就没有歧义。5.3 INF 设成 INT_MAX 导致最短路全错现象Dijkstra 或 Bellman-Ford 跑完后所有不可达点的距离全是 INT_MAX且可达点的距离也被污染。原因INT_MAX w溢出成负数dis[v] dis[u] w的比较完全失效。解决统一用0x3f3f3f3f约 10.6 亿加上常见边权仍在 int 范围内。如果距离数组是long long用0x3f3f3f3f3f3f3f3f作为 LL 级无穷大。5.4 快速幂里 a*a 溢出导致取模错误现象quickMi(a, b, p)在 p 接近 1e18 时输出负数或结果不稳。原因a * a是两个 long long 相乘如果 a 本身接近 1e9平方约 1e18接近 long long 上限 9.22e18一旦越界% p的结果就无意义。解决p 小于等于 1e9 时a a * a % p安全p 接近 1e18 时把平方操作改为a quickMul(a, a, p)用加法取模替代乘法。竞赛里 p 取 1e97 不用担心但如果换成其他大模数一定要检查这一步。5.5 Lucas 定理要求 p 是素数现象p 是合数时C(a, b, p)的结果和暴力求解完全不同。原因C()里用quickMi(i, p-2, p)算逆元但费马小定理只在 p 是素数时成立p 是合数时这个指数运算不是逆元。解决确认题目的 p 是否为素数。是素数就放心用 Lucasp 是合数时改用扩展 Lucas 算法或把 p 质因数分解后对每个素数幂分别计算再用中国剩余定理合并。不要在小规模样例上看到结果对了就以为没问题——小数数据在 p 为素数时的正确性不代表 p 为合数时也正确。6. 把模板变成自己的对拍验证与一处泛化改造6.1 先对拍再上战场拿到模板后我会先写一个随机数据生成器再配一个暴力计算程序。生成器产生小规模输入暴力程序算出权威答案模板程序跑出结果三个放一起对比不一致就停下来修。生成器大致长这样// 生成 100 组 a, bp 固定为 1e97 int T 100; printf(%d\n, T); while (T--) { int a rand() % 1000000 1; int b rand() % a 1; printf(%d %d 1000000007\n, a, b); }把生成器输出分别喂给暴力程序和模板程序再用 diff 比对两个输出文件。有一次不一致就把那组数据抠出来手工查。这个流程能覆盖掉绝大多数边界坑递归边界、取模为 0、负数输入、大数溢出。我每次赛前都会把快读、快速幂、组合数学这几个核心函数跑一遍对拍确认现场没改坏东西。6.2 泛化改造把快读变成模板函数原模板的read()只支持 int但比赛里long long输入同样常见。我会把它改写成函数模板template class T inline T read() { T x 0, f 1; char c getchar(); while (c ! - (c 0 || c 9)) { if (c EOF) return T(-1); c getchar(); } if (c -) { f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }调用处写LL x readLL();int 写int y readint();一个函数覆盖两种类型省去维护两套函数。注意返回 EOF 时强转成T(-1)保证调用方用! -1判断时类型一致。如果你想更进一步可以仿照 quickMul 的思路把整套数论模板迁移到矩阵快速幂——矩阵乘法里的取模与溢出处理和这里的快速幂同构改起来不费劲。这个模板我用了好几场正式比赛最深的体会是模板不能只靠「抄对了」来保证正确赛前对拍才是稳妥习惯。有一次我改造read()时把负号判断丢了小数据全对、大数据全错最后靠对拍定位到是快读问题。从那以后每次赛前都强制走一遍「随机数据 暴力对拍」的流程确认无误再收进模板库。希望帮到你。本文还有配套的精品资源点击获取