1. 从一道集训题看多项式相等的判定逻辑相等的多项式这个标题第一次看到的人可能会觉得平平无奇——两个多项式相等不就是系数对应相等吗但真正在竞赛集训里做过这类题的人都知道这里面藏着的坑远比想象中多。它涉及多项式表示、模运算、哈希思想、随机化算法等一系列知识点是一道非常典型的看起来简单、做起来要命的题目。我在带集训队的时候发现很多同学拿到这类题的第一反应就是逐项比较系数然后写完发现要么超时要么被特殊数据卡掉。问题的核心在于多项式可能以非常隐蔽的形式给出比如因式分解形式、点值形式、递推形式甚至是通过某种操作间接定义的。你根本没有办法直接拿到系数向量去做比较。这篇文章适合正在准备算法竞赛的选手、对多项式处理感兴趣的开发者以及想了解随机化算法在实际问题中如何应用的学习者。我会从题目可能的几种出题形态出发逐一拆解判定思路重点讲清楚哈希方法为什么有效、怎么选参数、以及那些只有踩过坑才知道的细节。2. 多项式相等的本质系数向量还是函数行为2.1 系数表示下的直接比较最朴素的理解是两个多项式相等当且仅当它们同次项的系数完全相同。如果题目直接给你两个系数数组那确实一个循环就能解决。但竞赛题不会这么善良。通常的情况是多项式通过某种操作序列生成比如多次乘法、加法、求导、积分等。你可以在每一步维护系数向量但问题是系数会爆炸式增长。举个例子如果初始系数是两位数经过几十次多项式乘法之后系数可能达到几千位数字。这时候每次运算都是大数运算时间复杂度直接起飞。所以直接维护系数向量在大多数情况下不可行。你需要换一个角度来思考相等这件事。2.2 函数视角下的相等判定从函数的角度看两个多项式相等意味着对于定义域内的每一个取值它们的函数值都相同。这给了我们一个全新的思路不需要比较系数只需要比较函数值。但这里有个关键问题你不可能枚举所有可能的取值。多项式定义在实数域或某个有限域上取值有无穷多个或模数那么多个。怎么办这就引出了随机化算法的核心思想如果我随机选取若干个点两个多项式在这些点上的取值都相同那么它们大概率是相等的。为什么是大概率而不是一定因为存在这样的可能性两个不同的多项式恰好在所有选取的点上都取相同的值。但根据代数基本定理一个非零多项式的零点个数不超过它的次数。所以如果我们选取的点足够多且多项式次数有上界那么误判的概率可以被控制得非常低。2.3 单点哈希与多点验证的取舍实际做题时最常见的做法是选取一个大素数作为模数然后随机取一个或几个求值点计算多项式在该点的值比较两个多项式的值是否相同。单点验证的误判概率大约是多少如果模数是 ( p )多项式次数不超过 ( n )那么随机选一个点两个不同多项式在该点取值相同的概率不超过 ( n/p )。当 ( p ) 取 ( 10^9 ) 级别、( n ) 取 ( 10^5 ) 级别时误判概率大约是 ( 10^{-4} )这个概率在竞赛中通常是可以接受的但如果你不放心可以取两个不同的模数或者两个不同的求值点把误判概率降到 ( 10^{-8} ) 以下。注意选取模数时一定要选大素数不要选合数。合数会导致零因子问题使得乘积为零不能推出某个因子为零从而破坏哈希的正确性。3. 出题人可能设置的四种变形与应对策略3.1 因式分解形式给出的多项式有些题目会以 ((x-a_1)(x-a_2)\cdots(x-a_n)) 的形式给出多项式要求你判断两个这样的乘积是否相等。这时候你当然可以逐项展开但展开的复杂度是 ( O(n^2) ) 的在 ( n ) 达到 ( 10^5 ) 时完全不可行。正确的做法是选取一个随机点 ( r )分别计算两个乘积在 ( r ) 处的值。计算乘积的值只需要 ( O(n) ) 时间——把每个因子在 ( r ) 处的值算出来然后乘起来就行。如果两个乘积在 ( r ) 处的值相同就认为它们相等。这里有个细节如果某个因子在 ( r ) 处的值为零那么整个乘积为零。两个乘积都为零并不能说明它们相等因为可能一个乘积的某个因子恰好被 ( r ) 整除另一个乘积的另一个因子被 ( r ) 整除。不过这种情况发生的概率很低因为 ( r ) 是随机选取的而每个因子被 ( r ) 整除的概率只有 ( 1/p )。3.2 点值形式给出的多项式另一种常见的变形是题目给你两个多项式在一组点上的取值要求你判断它们是否相等。这时候你可能会想直接比较这些点上的值不就行了但问题在于题目给出的点可能不够多或者两个多项式在给出的点上恰好相同但在其他点上不同。你需要验证的是多项式作为函数的整体行为而不仅仅是有限个点上的行为。应对方法是如果题目给出的点集大小超过了多项式的次数上界那么在这些点上全部相同确实可以推出多项式相等。但如果点集不够大你就需要自己补充随机点进行验证。具体来说你可以把多项式用拉格朗日插值还原出系数然后再比较系数。但插值的复杂度是 ( O(n^2) ) 的在 ( n ) 较大时不可行。更实用的做法是直接在随机点上求值。如果你能通过某种方式在 ( O(n) ) 时间内计算多项式在任意点的值比如利用点值表示的特殊结构那就直接算。如果不能可能需要结合其他技巧。3.3 递推或操作序列定义的多项式这是最难处理的一种情况。多项式不是显式给出的而是通过一系列操作加法、乘法、复合、求导等间接定义的。你需要在执行这些操作的过程中维护某种哈希值。关键技巧是哈希函数需要与多项式运算兼容。具体来说如果你用在随机点 ( r ) 处求值作为哈希那么加法( (fg)(r) f(r) g(r) )乘法( (f \cdot g)(r) f(r) \cdot g(r) )求导( f(r) ) 不能直接从 ( f(r) ) 得到需要额外维护导数的哈希值对于求导操作你需要同时维护 ( f(r) ) 和 ( f(r) )。求导的链式法则和乘积法则在哈希值上同样适用。如果涉及复合操作还需要维护更多信息。3.4 模意义下的多项式与整数系数的区别有些题目中的多项式是在模 ( p ) 意义下定义的有些则是在整数意义下定义的。这两者有本质区别。在模 ( p ) 意义下( x^p - x ) 和零多项式在所有点上的取值都相同费马小定理但它们是不同的多项式。所以如果你在模 ( p ) 下做哈希需要确保多项式的次数小于 ( p )否则会出现这种伪相等的情况。在整数意义下系数可能非常大直接计算哈希值时需要注意溢出问题。通常的做法是选取一个足够大的模数使得哈希值不会溢出或者使用多模数哈希。4. 哈希参数选择的实战经验4.1 模数的选取为什么推荐 ( 10^97 ) 和 ( 998244353 )在竞赛中最常用的两个模数是 ( 10^97 ) 和 ( 998244353 )。前者是经典的素数模数后者是 ( 119 \times 2^{23} 1 )支持快速数论变换NTT。对于多项式哈希来说这两个模数都够大单点误判概率在 ( 10^{-4} ) 以下。如果你需要更低的误判概率可以同时使用这两个模数把误判概率降到 ( 10^{-8} ) 以下。但要注意不要使用 ( 10^97 ) 和 ( 10^99 ) 这样的相邻素数组合。因为如果某个多项式的系数在其中一个模数下恰好为零在另一个模数下也很可能为零两个模数的哈希值会同时失效。选取模数时最好让它们之间没有简单的线性关系。4.2 随机点的选取不要用固定值很多同学为了图方便直接取 ( r1 ) 或 ( r2 ) 作为求值点。这在大多数情况下没问题但如果出题人故意构造了针对这些点的数据你就会挂得很惨。正确的做法是使用随机数生成器选取 ( r )。在竞赛中常用的随机数生成方式是mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int r rng() % mod;如果你担心随机数生成器的质量可以结合多个随机源或者使用固定的大素数加上随机偏移。提示在某些平台上rand()函数的随机性可能不够好建议使用 C11 的mt19937或手写一个简单的 xorshift 生成器。4.3 多点验证的代价与收益单点验证的误判概率是 ( n/p )双点验证的误判概率是 ( (n/p)^2 )。当 ( n10^5 )、( p10^9 ) 时单点误判概率约为 ( 10^{-4} )双点约为 ( 10^{-8} )。双点验证的代价是计算量翻倍。如果你的算法本身已经是 ( O(n \log n) ) 的翻倍可能还能接受。但如果已经是 ( O(n^2) ) 的翻倍就可能导致超时。我的建议是如果时间限制宽松用双点验证求稳如果时间紧张用单点验证加一个大模数同时在代码中做好心理准备——万一被卡了那就是运气问题。4.4 处理负数系数和取模运算的细节在计算哈希值时如果系数可能为负数需要先取模再运算。C 中负数取模的结果是负数需要手动调整int norm(int x) { if (x 0) x mod; if (x mod) x - mod; return x; }另外在多项式乘法中如果使用快速数论变换NTT需要确保模数支持原根。( 998244353 ) 的原根是 ( 3 )( 10^97 ) 的原根是 ( 5 )。使用错误的原根会导致变换结果错误。5. 完整实现从读入到输出的全流程拆解5.1 数据读入与预处理假设题目给出两个多项式每个多项式以操作序列的形式给出。你需要先解析操作序列然后逐步计算哈希值。读入时要注意操作的类型和参数可能在同一行也可能分行给出参数的范围可能很大需要用long long存储如果操作涉及除法需要转换为乘以逆元预处理阶段你需要预先计算好所有可能用到的逆元。如果模数是素数可以用费马小定理求逆元如果模数不是素数需要用扩展欧几里得算法。5.2 核心哈希计算模块核心模块负责在给定点 ( r ) 处计算多项式的值。根据操作类型的不同计算方式也不同操作类型哈希值计算方式常数 ( c )( c \bmod p )加法 ( fg )( (H(f) H(g)) \bmod p )乘法 ( f \cdot g )( (H(f) \cdot H(g)) \bmod p )求导 ( f )需要额外维护 ( H(f) )复合 ( f(g) )需要递归计算或使用泰勒展开对于求导操作维护两个哈希值( H(f) f(r) ) 和 ( H(f) f(r) )。求导的规则是( (fg) f g )( (f \cdot g) f \cdot g f \cdot g )在哈希值上同样适用这些规则。5.3 比较与输出计算完两个多项式在 ( r ) 处的哈希值后直接比较是否相等。如果相等输出YES否则输出NO。如果你使用了双点验证需要两个点上的哈希值都相等才输出YES。输出格式要注意题目要求有些题目要求输出YES/NO有些要求输出Equal/Not Equal还有些要求输出具体的差异信息。仔细阅读题目描述不要在这上面丢分。5.4 完整代码框架#include bits/stdc.h using namespace std; const int MOD 998244353; const int G 3; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int norm(int x) { if (x 0) x MOD; if (x MOD) x - MOD; return x; } int power(int a, int b) { int res 1; while (b) { if (b 1) res 1LL * res * a % MOD; a 1LL * a * a % MOD; b 1; } return res; } int inv(int x) { return power(x, MOD - 2); } struct PolyHash { int val, der; // f(r) and f(r) PolyHash(int v 0, int d 0) : val(v), der(d) {} PolyHash operator(const PolyHash o) const { return PolyHash(norm(val o.val), norm(der o.der)); } PolyHash operator*(const PolyHash o) const { return PolyHash( 1LL * val * o.val % MOD, (1LL * der * o.val 1LL * val * o.der) % MOD ); } }; int main() { int r rng() % MOD; // 读入并计算两个多项式的哈希值 // ... return 0; }6. 那些年我踩过的坑与排查实录6.1 模数选错导致哈希冲突有一次集训赛我选了一个看起来很大的模数 ( 10^99 )结果被出题人卡了。后来分析发现出题人构造了两个不同的多项式它们的系数在 ( 10^99 ) 下恰好满足某种线性关系导致哈希值相同。排查过程我先用暴力算法在小数据上验证发现小数据都过了大数据才挂。然后我换了模数 ( 998244353 )问题就解决了。这说明模数的选取确实会影响正确性不能随便选。经验教训尽量使用经过验证的模数或者使用双模数。如果时间允许可以在代码中同时用两个模数计算只有两个模数下的哈希值都相同才认为多项式相等。6.2 随机点选取不当导致误判还有一次我为了调试方便把随机点固定成了 ( r1 )。结果有一组数据专门针对 ( r1 ) 构造两个多项式在 ( r1 ) 处取值相同但实际不同。我挂了这组数据。排查过程我把随机点改成运行时生成问题就消失了。这让我意识到固定随机点虽然方便调试但在正式提交时一定要改成随机生成。经验教训调试时可以用固定随机点但提交前一定要改回随机。可以在代码中加一个宏调试时定义DEBUG提交时注释掉。6.3 求导操作忘记维护导数哈希在涉及求导的题目中我一开始只维护了 ( f(r) )没有维护 ( f(r) )。结果在计算 ( (f \cdot g) ) 时无法正确计算。排查过程我手动模拟了一个简单的例子发现乘积的导数需要用到 ( f(r) ) 和 ( g(r) )。于是我修改了哈希结构体增加了der字段并在乘法操作中正确更新。经验教训在设计哈希结构时要提前考虑所有可能的操作。如果题目涉及求导一定要同时维护函数值和导数值。6.4 大数运算溢出问题在计算哈希值时我使用了int类型存储中间结果。结果在乘法时两个接近 ( 10^9 ) 的数相乘结果超过了int的范围导致溢出。排查过程我加了调试输出发现哈希值变成了负数。后来把中间结果改成long long问题就解决了。经验教训在模运算中乘法一定要用long long存储中间结果。即使最终结果在int范围内中间乘积也可能溢出。6.5 多测数据未清空全局变量有一道题有多组测试数据我在每组数据之间没有清空全局数组导致上一组的数据影响了下一组的结果。排查过程我在每组数据开始处加了清空操作问题就解决了。这个坑很隐蔽因为单组数据时完全正常只有多组数据才会暴露。经验教训写多测题目时一定要在每组数据开始处清空所有全局变量。可以在代码中定义一个init()函数专门负责清空工作。7. 从这道题延伸出的通用方法论7.1 随机化算法的适用场景与局限性随机化算法在竞赛中非常实用但并不是万能的。它的适用场景是你需要判断两个对象是否相等但直接比较的代价太高。通过哈希你可以把比较的代价降到 ( O(1) ) 或 ( O(\log n) )。局限性在于随机化算法只能给出大概率正确的答案不能保证百分之百正确。在正式比赛中如果题目对正确性要求极高可能需要使用确定性算法。但在大多数情况下随机化算法的误判概率已经足够低可以放心使用。7.2 哈希思想在其他问题中的应用多项式哈希只是哈希思想的一个应用。类似的思想还可以用于字符串匹配把字符串看作多项式比较哈希值树同构判定把树哈希成一个整数比较哈希值图同构判定把图哈希成一个整数比较哈希值集合比较把集合哈希成一个整数比较哈希值核心思想都是一样的把复杂的对象映射到一个简单的值通过比较值来判断对象是否相等。7.3 如何设计一个可靠的哈希方案设计哈希方案时需要考虑以下几点模数要足够大且最好是素数随机点要真正随机不能固定如果可能使用多个模数或多个随机点注意处理负数、溢出等边界情况在多测题目中每组数据都要重新生成随机点提示如果你不确定哈希方案是否可靠可以在本地用暴力算法对拍。生成大量随机数据比较哈希算法和暴力算法的结果。如果多次对拍都一致说明哈希方案基本可靠。7.4 竞赛中时间与正确性的权衡在竞赛中时间限制和正确性往往需要权衡。使用双模数哈希可以提高正确性但会增加运行时间。使用单模数哈希速度快但误判概率略高。我的建议是如果时间限制宽松比如 ( 2 ) 秒以上用双模数哈希如果时间紧张比如 ( 1 ) 秒用单模数哈希加随机点。如果还是担心可以在代码中加入一个保险机制当哈希值相等时再用暴力算法验证一小部分数据。如果暴力验证也通过就输出YES。这个保险机制在实际比赛中非常实用。它可以在几乎不增加运行时间的情况下大幅降低误判概率。因为大多数情况下两个多项式确实相等暴力验证会很快通过只有当两个多项式不同但哈希值相同时暴力验证才会失败而这种情况发生的概率极低。7.5 从集训题到工程实践的思维迁移这道集训题看似只是竞赛中的一个小知识点但它背后的思想在工程实践中同样有用。比如在分布式系统中你需要判断两个节点上的数据是否一致直接比较所有数据的代价太高就可以使用哈希。在版本控制系统中Git 使用 SHA-1 哈希来标识文件内容本质上也是同样的思想。所以不要觉得竞赛题只是为了比赛。它训练的是你的算法思维和问题解决能力这些能力在工程实践中同样重要。我在实际工作中多次用到哈希思想来解决数据一致性问题效果非常好。最后分享一个小技巧如果你在比赛中遇到了多项式相等的题目但不确定自己的哈希方案是否可靠可以先写一个暴力算法然后用对拍来验证。对拍是竞赛中非常实用的调试技巧可以帮助你快速发现代码中的问题。具体做法是写一个数据生成器生成大量随机数据然后分别运行暴力算法和哈希算法比较结果。如果多次对拍都一致说明哈希算法基本可靠。如果发现不一致就找到了一个反例可以针对这个反例分析问题所在。