企业官网建设流程全解析

简介：这是一份专为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 // 把 pair<int,int> 简写为 pii，输出调试信息时省事 #define pii pair<int, 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写成n+1，这是宏定义最常见的翻车点。

宏定义还有一个伴随 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 项（F0=0, F1=1） 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) = a，ax + 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[i+1] * (i+1) % 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[i+1] * (i+1)，因为i! * inv_fac[i] ≡ 1，而(i+1)! * inv_fac[i+1] ≡ 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 = 10，Lucas 完全失效，因为 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

现象：模数约1e18，res * 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。

本文还有配套的精品资源，点击获取