简介这是一份专为ACM竞赛选手整理的C算法基础模板以单个PDF文件打包大小仅53KB内容涵盖竞赛高频使用的宏定义、快读快写、快速幂、最大公约数GCD与最小公倍数LCM、扩展欧几里得算法、组合数计算及Lucas定理。文档从宏定义开篇介绍FAST、X/Y、LL/ULL、PII等常用别名与常量预设帮助选手在比赛现场省去重复定义快读快写部分给出基于字符逐位解析的整数输入输出函数避免流同步开销与多余空格/负号判断GCD/LCM、扩展欧几里得和快速幂/快速乘模板均给出可直接复制使用的函数注释清晰适合在赛前快速搭建个人模板库。组合数与Lucas定理部分则针对大数取模场景提供递归与迭代两种计算路径便于处理a、b超出模数时的组合数问题。整体结构紧凑、实用性强已有531人浏览学习适合正在准备ACM/ICPC等算法竞赛、希望摆脱重复造轮子的初学者和进阶选手。1. ACM基础模板拿它当起跑线之前先明白它帮你省掉的是什么写 ACM 题最难受的时刻不是推导不出公式而是思路全对、代码写到一半突然被一个输入输出卡到超时或者因为 gcd 写成了嵌套循环而错过一整个 Accepted。这份《ACM基础模板宏定义、快读快写、快速幂、gcd、组合数与Lucas定理》本质上是把竞赛里最常用、最容易被忽略的底层零件打包在一起让你不用每次重新造轮子。它解决的是三件事让输入输出不再成为性能瓶颈、让大数运算不再溢出、让组合数取模能在题目限制内跑完。适合刚入门 ACM 的在校学生、准备机试的求职者以及那些板子散落各处、每次复制粘贴还要改半天的老手。模板不是银弹但把它读透、改造成自己的风格能省下大量比赛中的无效时间。2. 宏定义与快读快写把输入输出的时间黑匣子拆开2.1 宏定义先别急着抄命名冲突和副作用才是真正的坑很多模板把宏定义放在最前面因为竞赛代码要求短平快#define int long long这类写法能省不少事。但宏定义是有代价的它发生在预处理阶段编译器不检查类型也不遵守作用域规则。常见做法是把所有宏集中放在一个头文件区域用#ifndef包裹防止重复包含。比如#pragma once // 防止重复包含的宏开关 #ifndef ACM_TEMPLATE_H #define ACM_TEMPLATE_H #include bits/stdc.h using namespace std; // 类型简写把 long long 简写为 ll减少代码噪音 #define ll long long #define ull unsigned long long // 把 pairint,int 简写为 pii输出调试信息时省事 #define pii pairint, int // 遍历容器的简写配合 auto 使用 #define rep(i, a, b) for (int i (a); i (b); i) #define per(i, a, b) for (int i (b)-1; i (a); --i) // 取绝对值的内联函数比宏更安全 template typename T T abs(T x) { return x 0 ? -x : x; } #endif逻辑说明#pragma once和#ifndef的作用是防止同一个头文件被 include 多次导致重复定义错误这在模板被拆成多个文件时尤其重要。rep和per是 ACM 圈最常见的循环宏把for(int i 0; i n; i)压缩成一行。参数说明#define rep(i, a, b)里的a和b分别是循环起点和终点注意这是左闭右开区间i从a到b-1。如果题目要求闭区间一定要在调用处把b写成n1这是宏定义最常见的翻车点。宏定义还有一个伴随 ACM 选手整个赛季的阴影——#define int long long。这个宏能解决 int 溢出问题但会带来两个隐藏代价一是所有main函数必须写成signed main()否则编译器报错二是内存占用翻倍当题目卡 64MB 内存时原本用 int 能过的题换成 long long 可能直接 MLE。我一般只在题目明确说明数值范围超过2^31-1时才开这个宏而不是默认开启。另外宏定义数组长度#define MAXN 100005这类写法虽然经典但要留意题目可能把上限调到 200000写死数字不如const int MAXN 1e5 5;可维护。2.2 快读快写getchar、fread 还是 ios::sync_with_stdio(false)输入输出是 ACM 赛场上最简单也最玄学的一环。同一个程序用cin和用scanf跑出来的时间可能差三倍而用快读能再压一个量级。核心原理是cin/cout默认与 C 标准 IO 同步每次输入都要做同步检查开销很大。ios::sync_with_stdio(false)切断这个同步后cin的速度接近scanf但这还不够。当输入规模达到 1e6 级别时getchar逐字符读取本身就比scanf的格式化解析快得多。// 快读模板支持正负整数 inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { // 跳过所有非数字字符 if (c -) f -1; // 记录负数符号 c getchar(); } while (c 0 c 9) { x (x 3) (x 1) (c ^ 48); // 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函数的核心思路是跳过前导空白和符号位然后逐位累加。(x 3) (x 1)等价于x * 10位移运算比乘法快一点这是模板里常见的微优化。c ^ 48等价于c - 0因为数字字符的 ASCII 码与数值恰好相差 48。参数说明这个快读只支持 int 范围如果要读 long long把int x改成ll x。注意write函数用递归实现如果数值有 1e9 那么大会递归 10 层不用担心栈溢出但如果写成循环版需要先倒序存入字符数组再正序输出反而更麻烦。当输入规模达到 1e7 以上getchar的逐字符调用也会有开销这时候需要上fread缓冲区读取// fread 快读一次性读入整个输入流到缓冲区 const int BUFSIZE 1 20; char buf[BUFSIZE], *p1 buf, *p2 buf; inline char getChar() { if (p1 p2) { p2 buf fread(buf, 1, BUFSIZE, stdin); // 缓冲区读空后重新填充 p1 buf; } return *p1; }参数说明BUFSIZE取1 20约 1MB是空间和时间的折中再大收益不明显反而增加缓存压力。p1是当前读取位置p2是缓冲区有效末尾当p1追上p2说明缓冲区读空需要从 stdin 重新读入。这种实现比getchar快约 30%但代码复杂度上升。初学者建议先用getchar版本等真正遇到卡 IO 的题再换fread。输出端的同理putchar逐字符输出在极限数据下也会成为瓶颈可以用fwrite攒一批再统一输出不过大多数题目用不到。3. 快速幂与gcd从二进制拆分到矩阵加速的数论地基3.1 快速幂算法C为什么它能从 O(n) 降到 O(log n)快速幂解决的是a^b mod p的计算问题。朴素的循环乘法要做 b 次当 b 取到 1e18循环到比赛结束都跑不完。快速幂的核心思想是把指数拆成二进制比如a^13 a^8 * a^4 * a^1因为 13 的二进制是 1101只需要做 3 次乘法而不是 13 次。这个思路在密码学、组合数计算、矩阵快速幂里处处复用。// 迭代版快速幂求 a^b % mod ll qpow(ll a, ll b, ll mod) { ll res 1; a % mod; // 防止 a 本身大于 mod while (b 0) { if (b 1) res res * a % mod; // 当前二进制位为 1累乘结果 a a * a % mod; // a 自乘对应二进制位的权值 b 1; // 指数右移处理下一位 } return res; }逻辑说明b 1判断当前最低位是否为 1如果是则把当前的a乘入结果。a a * a是因为指数每右移一位底数要平方一次来对应新的权值。整个过程相当于把指数b的二进制位从左到右处理一遍循环次数等于b的二进制位数即O(log b)。参数说明mod传 0 时函数会崩溃因为% 0是未定义行为实际使用中要保证模数大于 1。res的初始值恒为 1这是乘法的单位元如果改成加法快速幂则初始化为 0。矩阵快速幂是快速幂的直接推广把a换成矩阵乘法换成矩阵乘法。它最常见的应用是斐波那契数列F(n) F(n-1) F(n-2)可以用 2x2 矩阵表示状态转移求F(1e18)只靠递推不可能但矩阵快速幂在O(log n)内就能算出来。实现时要注意矩阵乘法不满足交换律代码里乘法的顺序不能调换// 2x2 矩阵快速幂求斐波那契第 n 项F00, F11 struct Mat { ll m[2][2]; Mat(bool isIdentity false) { memset(m, 0, sizeof(m)); if (isIdentity) { m[0][0] m[1][1] 1; } } }; Mat mul(Mat A, Mat B, ll mod) { Mat C; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) C.m[i][j] (C.m[i][j] A.m[i][k] * B.m[k][j]) % mod; return C; }逻辑说明Mat(bool isIdentity)构造函数用默认参数生成零矩阵或单位矩阵单位矩阵是矩阵乘法中的单位元作用等同快速幂里的res 1。mul函数实现 2x2 矩阵乘法三重循环的中间变量k是矩阵乘法的公共维度。参数说明如果题目需要 3x3 或更高维矩阵直接把数组维度改大但维度超过 100 时三重循环会退化到O(n^3 log b)那时候要考虑 Strassen 算法或降低维度。矩阵快速幂的模数同样不能为 0而且矩阵中的元素乘法可能溢出 long long当mod大于sqrt(9e18) ≈ 3e9时需要改用__int128做中间乘法。3.2 gcd与扩展欧几里得不只是辗转相除gcd最大公约数是数论题的地基。C 的algorithm头文件自带std::gcd但很多模板仍保留手写版本原因是需要配套实现扩展欧几里得exgcd它能在求出 gcd 的同时得到一组 x, y 使得ax by gcd(a, b)。这组解是求解模逆元、一次同余方程的基础。// 标准欧几里得递归版 gcd ll gcd(ll a, ll b) { return b 0 ? a : gcd(b, a % b); } // 扩展欧几里得求出 x, y 使得 ax by gcd(a, b) ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; // 此时 gcd(a, 0) aax 0*y a return a; } ll d exgcd(b, a % b, y, x); // 递归交换 x, y 的位置 y - a / b * x; // 回溯调整 y 的值 return d; }逻辑说明exgcd的递归终止条件是b 0此时gcd(a, 0) a一组平凡解是x 1, y 0。回溯时通过y - a / b * x把上一层的解调整为本层的解这一步的数学推导是展开a % b a - (a/b)*b后整理得到的。参数说明x和y使用引用传递函数返回的是gcd(a,b)解储存在引用参数里。如果题目要求 x 为非负最小解需要对解模b / d取正即x (x % (b/d) b/d) % (b/d)。gcd 在加速组合数计算时还有一个关键优化预处理所有数的质因数分解然后统计每个质因子的幂次来求 gcd。这在处理多组 gcd 查询时能把复杂度从O(log n)摊到接近O(1)。但竞赛里最常见的还是直接调std::gcd它内部已用 Stein 算法优化过比手写辗转相除更快。扩展欧几里得真正不可替代的场景是求模逆元当gcd(a, p) 1时a在模p意义下的逆元就是exgcd(a, p, x, y)得到的x模p的正值。这个逆元在组合数取模里大量使用连着下一章的 Lucas 定理一起理解会顺很多。4. 组合数与Lucas定理模意义下的大组合数到底怎么算4.1 预处理阶乘和逆元O(1) 查询组合数 C(n, m)组合数C(n, m)的定义是n! / (m! * (n-m)!)。直接算阶乘再相除数值会爆炸——C(100, 50)就已经是一个 29 位的大整数。竞赛里几乎所有组合数题都要求结果对某个模数取模于是问题变成C(n, m) mod p。朴素做法是对每个查询重新算阶乘复杂度 O(n) 一次多次查询就超时。预处理阶乘表加逆元表能把单次查询压到 O(1)const int MOD 1e9 7; const int MAXN 100005; ll fac[MAXN], inv_fac[MAXN]; // 快速幂求逆元费马小定理a^(p-2) ≡ a^(-1) (mod p)要求 p 是素数 ll qpow(ll a, ll b, ll mod) { ll res 1; a % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } void precompute(int n, int p) { fac[0] 1; for (int i 1; i n; i) fac[i] fac[i-1] * i % p; // 费马小定理求 n! 的逆元再从后往前递推 inv_fac[n] qpow(fac[n], p - 2, p); for (int i n - 1; i 0; i--) inv_fac[i] inv_fac[i1] * (i1) % p; } // 组合数查询C(n, m) mod p ll C(int n, int m, int p) { if (m 0 || m n) return 0; // 非法参数直接返回 0 return fac[n] * inv_fac[m] % p * inv_fac[n-m] % p; }逻辑说明precompute先从前往后算出所有阶乘的模p值然后用费马小定理算出fac[n]的逆元再反向递推得到所有inv_fac。反向递推的性质是inv_fac[i] inv_fac[i1] * (i1)因为i! * inv_fac[i] ≡ 1而(i1)! * inv_fac[i1] ≡ 1两边整理后得到这个关系。参数说明p必须是素数MOD 1e9 7是竞赛最常用的模数因为它是素数且足够大乘法不会溢出 long long。如果模数不是素数费马小定理失效必须改用扩展欧几里得求逆元下一章会讲到这个坑。这套模板的适用边界是n不超过MAXN也就是预处理的范围。当n达到1e18级别阶乘表根本开不下必须用 Lucas 定理。判断什么时候用哪套最简单的经验法则题目给的n, m小于1e6直接预处理n, m巨大但模数p很小小于1e5用 Lucas。中间地带可以结合分段打表处理但竞赛题很少出到那种极端组合。4.2 Lucas定理小模数下处理超大组合数的数学捷径Lucas 定理说的是对素数p把n和m写成 p 进制形式n n0 n1*p n2*p^2 ...m m0 m1*p m2*p^2 ...那么C(n, m) ≡ C(n0, m0) * C(n1, m1) * ... (mod p)。这等于把一个大组合数拆成若干个小数位上的组合数相乘而每个小组合数的参数都不超过p-1可以用前面预处理的阶乘表直接算。// Lucas 定理递归版本p 是素数且小于 MAXN ll lucas(ll n, ll m, ll p) { if (m 0) return 1; // 递归出口m 为 0 时 C(n, 0) 1 // 分别取 n, m 的 p 进制最低位递归处理高位 return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p; }逻辑说明C(n % p, m % p, p)处理当前 p 进制位上的组合数lucas(n / p, m / p, p)递归处理高一位。因为n除以p相当于右移一位 p 进制递归深度等于log_p(n)n 1e18, p 100000时深度只有 3 层效率极高。参数说明C函数的第三个参数p要和 Lucas 的p保持一致否则阶乘表的逆元全部错位。注意这里的C函数需要访问fac和inv_fac数组而这两个数组的规模必须至少覆盖p - 1也就是说p不能超过MAXN。Lucas 定理最常见的翻车点是模数p不是素数。比如p 10Lucas 完全失效因为 p 进制拆分的数学前提是 p 为素数。处理合数模组合数要用中国剩余定理CRT合并几个素数模的结果那是更高一层的模板。另一个坑是p很大但n, m也很大比如p 1e9 7这时候 Lucas 退化到和直接预处理一样——n % p还是n本身递归一层的n/p变成 0 就结束了没有加速效果。Lucas 只在小素数模数场景发光这个边界一定要记住。5. 模板落地最常见的5个坑从编译到TLE的排查笔记5.1 #define int long long 导致 main 类型不匹配现象模板里加了#define int long long编译报main必须返回int或直接 CE。原因预处理把所有int替换成long long包括main函数的返回类型而标准规定main返回类型必须是int。解决把主函数写成signed main()signed不会被宏替换这是 ACM 圈的通用做法。另一个连带问题是scanf(%d, x)中的%d对应的是 int现在变量实际是 long long读入会截断数值。要么全部改成%lld要么用快读规避格式串匹配问题。5.2 快读遇到 EOF 死循环现象本地测试数据正常提交到 OJ 后 TLE程序像卡死一样。原因read()函数里的getchar()循环在读到 EOF返回 -1时c 0 || c 9恒真会一直循环下去。常见做法是从while循环变成for循环逐个处理输入但遇到文件末尾没有正确处理。解决把循环条件加上 EOF 判断inline int read() { int x 0, f 1; char c getchar(); while (c ! EOF (c 0 || c 9)) { if (c -) f -1; c getchar(); } while (c ! EOF c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }判断c ! EOF能确保读完最后一个数字后正常退出。还有一种隐蔽情况数据末尾是0 0表示结束的题容易被快读吞掉最后的结束标记需要在主循环里显式判断返回值后再决定是否终止。5.3 快速幂中间乘法溢出 long long现象模数约1e18res * a的结果超过9.2e18乘法溢出变成负数最终答案错误。原因long long最大9.22e18两个1e18级别的数相乘直接溢出。解决使用__int128做中间乘法再取模GCC 编译器直接支持不会增加太多代码ll mul_mod(ll a, ll b, ll mod) { __int128 res (__int128)a * b % mod; return (ll)res; }这个方法只适用于模数小于2^63的场景更大的模数需要 Montgomery 乘法这类进阶方案。竞赛里多数模数都是1e9级别不会遇到这个问题但遇到1e18级别的模数时这个坑很致命。注意__int128无法直接输入输出只能做中间运算。5.4 Lucas 定理用了非素数模数答案错得莫名其妙现象C(5, 2) % 4期望结果是10 % 4 2但用 Lucas 算出来是 0。原因Lucas 定理的成立条件要求模数p是素数p 4不满足条件公式推导中依赖的费马小定理完全失效。解决先用质数筛确认p是素数再决定是否走 Lucas。如果题目明确模数是合数但不太大可以分解质因数后分别用素数模算再用中国剩余定理合并。这个坑几乎没有预兆因为答案看起来往往是合法的整数只是数值不对非常难排查。5.5 预处理数组大小开小越界修改了相邻数组的值现象C(n, m)在n接近MAXN时结果不稳定或者输出奇怪的大数。原因fac[MAXN]只开到100005但n最大可能是100000模运算后索引n-m也接近MAXN数组fac[n]的最后几个位置访问越界改写了inv_fac的内存。解决数组开到MAXN 5而不是MAXN多出的几个位置作为缓冲另外在C函数入口加上if (n MAXN || m MAXN) throw或直接返回 0保证运行期不会越界。这个坑特别隐蔽因为越界不一定崩溃而是静默地弄乱相邻数据排查时要靠打印fac[i]和inv_fac[i]的相邻值对比才能发现。6. 验证这三件事模板才真正属于你模板拿到手不是复制粘贴就完了我用血的教训告诉你至少要验证三件事。第一件是对拍。随便写个暴力版的组合数函数、暴力版快速幂用随机小数据反复对比输出这是发现边界问题的唯一可靠手段。很多隐藏 bug 只在大数、模数恰好等于某些特殊值时暴露手动测试永远测不全面。第二件是压测性能。找一个n 1e6的输入文件用time命令分别测scanf和快读的耗时确认快读在你的机器上真实有效而不是想当然。我遇到过一次快读比自己写的cin关闭同步后还慢的情况因为cin内部有缓冲区优化而我的getchar版本没做缓冲数据量大时反而吃亏。第三件是把模板改造成自己能默写的程度而不是能搜索到的程度。比赛时没有时间翻模板文件快读、快速幂、exgcd 这些核心函数要练到闭着眼能写对组合数和 Lucas 要清楚适用边界。我自己的习惯是每场比赛后把用到的函数重新手写一遍并在代码注释里记录当场的坑。你面前的这份模板本质上是一条数学运算的流水线快读写入数据快速幂和 gcd 处理数论运算组合数和 Lucas 处理计数问题。把它读透之后建议你按自己的代码风格重构一遍——把read()改成你顺手的名字把宏定义精简到只用你真正需要的把MOD改成你常用的值。模板只有经过你的手改过才真正属于你。希望这些排错经验和边界理解能帮到你让你在赛场上少走几步弯路多争取几个 Accepted。本文还有配套的精品资源点击获取