1. 项目概述从两道算法题看竞赛核心思维最近在复盘一些经典的算法竞赛题目特别是2021年牛客暑期多校训练营第一场的两道题感触颇深。一场比赛里A题“博弈”和H题“快速傅立叶变换”看似风马牛不相及一个偏向数学逻辑推导一个偏向工程算法实现但它们恰好代表了算法竞赛中两种核心的解题能力抽象建模能力与复杂算法应用能力。很多选手可能对FFT这种“重型武器”心生畏惧或者觉得博弈论过于烧脑但实际比赛中它们往往是区分高手与普通选手的关键。今天我就结合这两道具体的题目拆解一下背后的解题思路、核心细节以及那些在标准题解里不会写的“踩坑”经验。无论你是正在备赛的选手还是对算法感兴趣的开发者相信这篇从实战角度的深度剖析都能给你带来一些新的启发。2. 题目A博弈——不止是猜拳更是逻辑的终极推演很多人一听到“博弈”第一反应就是石头剪刀布或者觉得是纯靠运气。但在算法竞赛的语境下博弈论题目几乎都是“完全信息公平组合游戏”运气成分为零比拼的是纯粹的逻辑推理和数学归纳能力。2021牛客多校1的这道A题正是这类问题的典型代表。2.1 核心问题抽象与模型建立这道题的具体描述通常是给定一个游戏局面比如一堆石子或者一个棋盘状态两名玩家轮流操作每次操作必须遵循既定规则比如取走一定数量的石子无法操作者判负。我们需要判断在双方都采取最优策略的情况下先手是必胜还是必败。这听起来很像经典的Nim游戏但多校的题目绝不会直接套用模板。它的难点往往在于你需要从题目描述中自己抽象出“局面”的定义和“操作”的规则并将其转化为一个可计算的模型。例如题目可能将石子排成一个序列每次操作与相邻石子的状态相关或者引入“能量”、“分数”等概念使得局面评估变得复杂。注意解决博弈题的第一步永远是彻底理解题意并尝试用自己定义的状态变量来描述游戏。不要一上来就想SG函数先手动模拟几个小规模实例感受胜负局面的规律。2.2 解题核心SG函数与动态规划的结合对于这类公平组合游戏最有力的理论工具是Sprague-Grundy定理SG定理。它将每一个游戏局面映射为一个非负整数SG值其中SG值为0的局面是“必败态”P-position即当前玩家无论怎么走对手都能将其引向另一个必败态或直接获胜。SG值不为0的局面是“必胜态”N-position即当前玩家存在至少一种操作可以将局面推向一个SG值为0的必败态。解题的通用框架如下定义状态用尽可能简洁的变量组合如一个整数、一个元组唯一表示一个游戏局面。确定终态明确哪些状态是无法操作的这些状态就是SG值为0的必败态起点。状态转移对于每一个非终态枚举所有合法的下一步操作。每个操作会将当前状态S转移到下一个状态T。那么状态S的SG值就是所有后继状态T的SG值组成的集合的mex值即不属于该集合的最小非负整数。计算答案根据初始状态计算其SG值。若SG值不为0则先手必胜否则先手必败。在实际编码中这通常通过记忆化搜索Memoization DFS或动态规划DP来实现。对于状态空间不大的题目可以直接计算所有状态的SG值。以一道简化版题目为例假设有一排n个格子某些格子里有石子。每次操作可以选取一个石子将其向左移动任意正数格但不能移出边界也不能越过或与其他石子重叠。无法移动者输。状态定义我们可以将石子的位置排序后作为一个元组。但由于石子间相互独立且移动只影响自身更优的做法是利用SG定理的“和”性质整个游戏的SG值等于每个石子单独游戏的SG值的异或和。因此我们只需要计算一个石子在某个位置时的SG值。状态转移一个石子在位置i可以移动到0, 1, ..., i-1假设从0开始编号。那么sg[i] mex{sg[0], sg[1], ..., sg[i-1]}。计算显然sg[0] 0无法移动。sg[1] mex{sg[0]} mex{0} 1。sg[2] mex{sg[0], sg[1]} mex{0, 1} 2。以此类推我们发现sg[i] i。答案初始时每个石子的位置是pos_k那么总SG值就是所有pos_k的异或和。若异或和非零先手胜。2.3 常见陷阱与优化技巧状态空间爆炸这是博弈DP最常遇到的问题。如果直接定义的状态变量维度高、范围大会导致无法计算。此时需要寻找规律或等效简化。寻找周期规律手动计算小规模数据的SG值观察其是否呈现周期性。很多题目在模某个数后SG值会循环。利用对称性/等价类有些不同的局面其实是等价的可以合并状态。打表找规律这是竞赛中的“黑科技”。写一个暴力程序计算小规模如n100所有状态的SG值然后观察输出尝试用数学公式或简单规律去拟合。在2021牛客这道题中很可能就需要这种技巧。误用SG定理SG定理要求游戏是“可分解的”即整体游戏可以看成若干子游戏的“和”且玩家每次只能在一个子游戏中进行操作。如果题目规则不符合这个条件例如一次操作同时影响多个子游戏则不能直接套用SG定理的异或和可能需要重新建模。记忆化搜索的细节在实现记忆化搜索时确保你的状态哈希函数高效且正确。使用unordered_map或手写哈希表时要注意碰撞。对于状态是整数的情况用数组存储效率最高。实操心得面对一道陌生的博弈题我的习惯是先花10-15分钟彻底理解规则并手工模拟然后尝试定义状态和转移评估状态数量如果数量巨大立即转向“打表找规律”的策略。多校级别的博弈题很少会让你轻松写出一个标准DP几乎都需要发现题目背后隐藏的数学模式。3. 题目H快速傅立叶变换——从理论到实战的跨越如果说博弈题考验的是“数学脑”那么FFT快速傅立叶变换题考验的就是“工程手”。你需要理解一个复杂的算法并能在时间限制内用代码正确无误地实现它。FFT是处理多项式乘法、高精度整数乘法、卷积等问题的利器能将O(n²)的复杂度降至O(n log n)。3.1 问题本质多项式乘法与卷积牛客多校H题大概率是这样一个问题给定两个多项式A(x)和B(x)求它们的乘积C(x)。多项式的系数可能非常大或者项数非常多n可达10^5甚至10^6级别直接使用双重循环的O(n²)算法必然超时。这正是指数函数和FFT的经典应用场景。两个n-1次多项式的乘法本质上就是求它们系数序列的卷积。FFT通过巧妙的数学变换在复数域上实现了离散傅里叶变换DFT的快速计算从而高效地求出卷积。3.2 FFT核心原理与算法步骤拆解理解FFT关键在于理解其如何利用单位根的周期性和对称性将一个DFT分解为规模更小的子问题分治思想。核心步骤点值表示法一个n次多项式可以由其在n1个不同点处的取值唯一确定。如果我们能快速得到A(x)和B(x)在一系列特定点x_k上的值那么乘积C(x)在这些点上的值就是A(x_k) * B(x_k)。最后我们再从这些点值反推出C(x)的系数。这个过程称为插值。单位根的选择FFT的精髓在于选择x_k为单位根即方程ω^n 1的复数解。它们具有完美的数学性质周期性ω^(kn) ω^k对称性ω^(kn/2) -ω^k当n为偶数时折半性(ω^k)^2 ω^(2k)是n/2次单位根。Cooley-Tukey算法流程预处理将多项式项数补足到2的整数次幂方便分治。DFT正向变换将系数表示法转换为点值表示法在单位根处取值。基于当前多项式在n个单位根处的值可以通过奇偶分项递归地计算两个规模为n/2的子多项式在n/2个单位根处的值再合并得到结果。非递归的实现迭代FFT效率更高它通过二进制位反转bit-reversal来重排系数然后进行自底向上的合并蝴蝶操作。点值相乘对A和B变换得到的点值序列逐点相乘得到C的点值序列。IDFT逆向变换将C的点值表示法转换回系数表示法。神奇的是IDFT的过程与DFT几乎完全相同只需将单位根取共轭并对最终结果除以n即可。蝴蝶操作Butterfly Operation是迭代FFT的核心它描述了合并两个小规模DFT结果的过程// 伪代码omega是当前层对应的单位根 Complex t omega * a[kjlen/2]; Complex u a[kj]; a[kj] u t; a[kjlen/2] u - t;3.3 从原理到代码手写FFT的注意事项虽然现在很多比赛允许使用STL的complex甚至有的语言有FFT库但手写一个高效、准确的FFT仍然是必备技能因为你可以针对具体问题如模数下的NTT进行定制。精度问题使用double和complex进行FFT时浮点数误差是最大的敌人。对于整数系数多项式最终结果需要四舍五入到最接近的整数。但当系数很大时误差可能导致取整错误。常见的应对策略是将每个系数拆成两个部分如高低位分别进行FFT最后合并相当于用浮点数模拟高精度运算。直接使用数论变换NTT。NTT是在模素数意义下用原根代替单位根进行的“整数FFT”完全避免了精度问题是竞赛中的首选。但要求模数p必须形如p c * 2^k 1且多项式长度n是2的幂且不超过2^k。边界处理与补零确保将多项式长度len扩展到不小于nmn和m是原多项式次数的最小的2的幂。数组要开足通常是len*2。迭代实现模板一个稳健的FFT模板应包括以下函数bit_reverse(): 对数组进行二进制位反转重排。fft(Complex a[], int len, int inv): 核心变换函数。inv1为DFTinv-1为IDFT。在IDFT后需要for i in range(len): a[i] / len;。主函数中读入系数补零对A和B分别做FFT点乘做IFFT输出取整后的系数。一个简化版的C核心代码框架#include complex #include cmath typedef std::complexdouble Complex; const double PI acos(-1.0); void bit_reverse(Complex a[], int len) { for (int i 0, j 0; i len; i) { if (i j) std::swap(a[i], a[j]); for (int l len 1; (j ^ l) l; l 1); } } void fft(Complex a[], int len, int inv) { bit_reverse(a, len); for (int h 2; h len; h 1) { Complex wn(cos(2 * PI / h), inv * sin(2 * PI / h)); for (int j 0; j len; j h) { Complex w(1, 0); for (int k j; k j h / 2; k) { Complex u a[k]; Complex t w * a[k h / 2]; a[k] u t; a[k h / 2] u - t; w * wn; } } } if (inv -1) { for (int i 0; i len; i) a[i] / len; } } // 主函数内使用 int len 1; while (len n m) len 1; // 补零到2的幂 fft(A, len, 1); // DFT A fft(B, len, 1); // DFT B for (int i 0; i len; i) C[i] A[i] * B[i]; // 点乘 fft(C, len, -1); // IDFT for (int i 0; i n m - 2; i) { printf(%d , (int)(C[i].real() 0.5)); // 四舍五入输出整数系数 }3.4 实战调试与性能优化验证正确性先用小规模数据n, m 10与暴力乘法O(n²)的结果对比确保算法逻辑正确。精度调试如果出现个别点取整错误检查是否是浮点误差累积所致。可以尝试在输出前加上一个微小的epsilon如1e-6再取整。对于极端数据考虑使用拆系数FFT或转用NTT。性能瓶颈FFT的常数较大。优化方法包括使用预处理的单位根数组避免在循环中重复计算cos和sin。使用C自带的std::complex它通常比手写复数类要快。对于NTT可以预处理原根的幂次。空间与时间权衡如果题目只要求卷积的某一项或者卷积有特殊性质如稀疏性可能不需要完整的FFT可以考虑其他算法。踩坑实录我第一次写FFT时忘了在IDFT后除以len导致结果大了无数倍调试了很久。另一个坑是单位根的角度计算2*PI/h中的h是当前合并段的长度不是总长度len这里搞错会导致全盘皆错。务必理解蝴蝶操作中每一层对应的单位根。4. 思维联结博弈与FFT的共通之处与备赛策略虽然A题和H题在知识点上差异巨大但深入来看它们对选手的要求有共通之处将实际问题转化为标准模型的能力博弈题需要将游戏规则转化为SG函数状态FFT题需要将问题可能是字符串匹配、高精度乘法、卷积求和转化为多项式乘法。这都要求强大的抽象能力。对经典模板的深刻理解与灵活改造博弈的SG定理、DP是模板FFT/NTT是模板。但比赛题目绝不会让你直接套模板。你需要知道模板的前提条件、适用范围和内部原理才能判断何时能用、怎么调整。比如博弈题状态需要压缩FFT题可能需要拆系数。数学工具的应用博弈论涉及组合数学、图论FFT涉及复变函数、数论NTT。算法竞赛的高级阶段数学功底至关重要。针对性的备赛策略对于博弈类题目掌握基础彻底理解Nim游戏、SG定理的证明和应用。专题练习集中刷一批不同变种的博弈题阶梯Nim、图上博弈、删边游戏等总结每种模型的特点和解题套路。培养“打表找规律”的敏感度这是解决陌生博弈题的最实用技巧。对于FFT/NTT类题目理解胜过背诵不要只抄模板。亲手推导一遍FFT的分治过程理解单位根的性质如何被利用。理解NTT中原根如何扮演单位根的角色。打造自己的可靠模板整理一个自己验证过无数遍、带有常用注释的FFT/NTT模板包括卷积、多项式求逆可选等常用函数。识别问题特征看到题目中出现“卷积”、“多项式乘法”、“所有两两之和/之积”等关键词要能立刻联想到FFT。将一场比赛中的不同题目关联起来看是提升竞赛水平的好方法。像这场多校赛可能就需要你在短时间内在严谨的逻辑推理A题和复杂的算法实现H题两种思维模式间快速切换。平时的训练除了刷题广度和深度也要注重这种“思维弹性”的锻炼。比如可以尝试在一次模拟赛中刻意先做一道数学构造题紧接着做一道数据结构题训练自己的大脑适应不同的思考节奏。最后无论是博弈还是FFT纸上得来终觉浅。看懂十篇题解不如自己动手实现一遍用各种边界数据去测试在“Wrong Answer”和“Time Limit Exceeded”中才能真正消化这些知识。遇到想不通的细节不妨画图——画状态转移图画蝴蝶操作的流程图很多问题在笔尖梳理的过程中就迎刃而解了。