从数论到博弈论：算法竞赛核心模板的实战精要与避坑指南

1. 算法竞赛模板的本质与价值

在ACM-ICPC、CCPC等算法竞赛中，"板子"（模板代码）是选手们经过长期实战验证的精华代码片段。这些模板的价值不仅在于其正确性，更在于它们体现了算法思想的精髓。对于初学者而言，理解这些模板背后的数学原理和实现细节，远比单纯记忆代码更为重要。

模板代码的三大核心价值 ：

• 可靠性 ：经过大量测试验证的正确实现
• 效率 ：针对竞赛环境优化的时间复杂度
• 复用性 ：模块化设计便于快速集成到解题中

提示：优秀的竞赛选手不仅要会使用模板，更要理解其数学原理和边界条件，这样才能在赛场上灵活调整。

2. 数论模板：从基础到高阶应用

2.1 质数判定的艺术

质数判定看似简单，实则暗藏玄机。试除法是最基础的实现，但竞赛中更常用的是Miller-Rabin概率性检测：

bool is_prime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

常见陷阱 ：

• 忽略1不是质数的特殊情况
• 循环条件写成 i*i <= n 可能导致整数溢出
• 没有预处理小质数表进行初步筛选

2.2 快速幂与模运算

快速幂算法是数论计算的基础，理解其二进制分解思想至关重要：

typedef long long LL;
int qmi(int a, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

关键点 ：

• 每一步乘法后立即取模防止溢出
• 处理k=0且p=1的特殊情况
• 结合费马小定理求逆元

3. 组合数学：计数问题的利器

3.1 组合数计算的四种方法

不同场景下需要选择最优的组合数计算方法：

方法	预处理复杂度	查询复杂度	适用场景
递推法	O(n²)	O(1)	n≤2000
逆元法	O(n)	O(1)	n≤1e5
Lucas定理	O(p)	O(logp n)	n≤1e18
质因数分解	O(n)	O(高精度)	需要精确值

递推法实现示例 ：

const int mod = 1e9 + 7;
int c[N][N];
void init() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}

3.2 卡特兰数的应用场景

卡特兰数在括号匹配、二叉树计数等问题中有广泛应用：

Cat(n) = C(2n,n)/(n+1)

典型应用 ：

• 合法括号序列数量
• 栈操作序列计数
• 凸多边形三角划分

4. 博弈论：SG函数与必胜策略

4.1 NIM游戏的核心定理

NIM游戏的胜负判定基于异或和：

int res = 0;
while (n--) {
    int x;
    scanf("%d", &x);
    res ^= x;
}
puts(res ? "Yes" : "No");

理解要点 ：

• 每堆石子的SG值就是其数量
• 总游戏的SG值是各堆SG值的异或
• 必胜策略：将异或和变为0的操作

4.2 SG函数的计算方法

SG函数是分析组合博弈问题的通用工具：

int sg(int x) {
    if (f[x] != -1) return f[x];
    unordered_set<int> S;
    for (int i = 0; i < m; i++) {
        int sum = s[i];
        if (x >= sum) S.insert(sg(x - sum));
    }
    for (int i = 0; ; i++)
        if (!S.count(i)) return f[x] = i;
}

使用技巧 ：

• 记忆化搜索优化计算
• mex运算找最小非负整数
• 游戏和的SG值等于各子游戏SG值的异或

5. 计算几何：向量与位置关系

5.1 点积与叉积的几何意义

struct Point { double x, y; };
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
double dot(Point a, Point b) { return a.x*b.x + a.y*b.y; }

应用场景 ：

• 叉积判断点线位置关系
• 点积计算投影长度
• 面积计算与方向判断

5.2 线段相交判断

bool segment_intersect(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2-a1, b1-a1), c2 = cross(a2-a1, b2-a1);
    double c3 = cross(b2-b1, a1-b1), c4 = cross(b2-b1, a2-b1);
    return sign(c1)*sign(c2) < 0 && sign(c3)*sign(c4) < 0;
}

注意事项 ：

• 考虑共线特殊情况
• 浮点数精度处理
• 边界条件测试

6. 数据结构与字符串处理

6.1 Trie树的高效实现

int tr[N][26], cnt[N], idx;
void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    cnt[p]++;
}

优化技巧 ：

• 数组实现比指针更快
• 动态分配节点内存
• 支持删除操作的实现

6.2 KMP算法的next数组

int ne[N];
void get_next(char *p) {
    for (int i = 1, j = 0; p[i]; i++) {
        while (j && p[i] != p[j]) j = ne[j-1];
        if (p[i] == p[j]) j++;
        ne[i] = j;
    }
}

理解要点 ：

• 前缀函数的概念
• 自我匹配的过程
• 优化匹配效率的原理

7. 实战中的调试技巧与性能优化

7.1 常见错误类型

• 整数溢出 ：使用long long，检查乘法运算
• 边界条件 ：空输入、极值测试
• 浮点误差 ：设定epsilon比较

7.2 调试方法

#define LOCAL
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif

有效策略 ：

• 对拍验证
• 小数据测试
• 输出中间结果

8. 模板的组织与管理

8.1 代码模块化设计

合理的模板组织能提升编码效率：

├── math/
│   ├── prime.cpp
│   ├── combinatorics.cpp
│   └── matrix.cpp
├── ds/
│   ├── segtree.cpp
│   └── union_find.cpp
└── geometry/
    ├── basic.cpp
    └── convex_hull.cpp

8.2 模板使用原则

1. 理解优先 ：确保明白算法原理
2. 适度修改 ：根据题目调整参数
3. 持续更新 ：淘汰低效实现
4. 分类测试 ：验证各模块正确性

在算法竞赛中，模板代码是利器而非拐杖。真正的高手能在理解的基础上灵活运用，甚至现场推导所需算法。建议初学者从简单模板入手，逐步深入理解其数学本质，最终达到能够根据问题特点调整甚至创新算法的水平。