1. 从一道集训题说起相等的多项式到底在考什么“相等的多项式”这个题目名字第一次看到的人多半会愣一下——多项式相等两个多项式长得不一样凭什么说它们相等这背后其实藏着一个在算法竞赛里非常经典的思维转换多项式作为形式对象它的相等性判断可以脱离数值代入转化为系数层面的逐项比对但一旦引入模运算或者多点求值问题就会瞬间变得有趣起来。我在带集训队的时候每年暑假都会遇到一批刚学完基础数论和组合数学的同学他们看到“多项式相等”的第一反应往往是“把 x 随便代几个值进去算出来一样就行了”。这个直觉不能说错但离严谨还差得远。举个最简单的例子在模 7 意义下多项式 f(x) x^7 - x 和 g(x) 0如果你只代入 x 0,1,2 去检验会发现两者确实相等但它们在系数层面完全不同。这就是费马小定理带来的“伪装相等”也是这类题目最爱设置的陷阱。所以这篇内容我想从一个集训参与者的视角把“相等的多项式”这个问题从头到尾拆一遍。不管你是正在准备算法竞赛的选手还是单纯对多项式理论感兴趣的开发者都能从中拿到可以直接用的思路和代码模板。我会重点讲清楚三件事多项式相等的严格定义是什么、在模意义下判断相等有哪些坑、以及如何用哈希和插值把复杂度压到可接受的范围。这些内容在常规教材里往往是分散的我尽量把它们串成一条线让你看完就能自己写出稳定的实现。2. 多项式相等的数学基础与常见误区2.1 形式相等与函数相等的本质区别在抽象代数里多项式首先是一个形式表达式也就是系数序列 (a_0, a_1, ..., a_n) 加上一个未定元 x 的形式组合。两个多项式相等严格来说是指它们的系数序列逐项相等和 x 取什么值没有任何关系。这个定义看起来很简单但它和“作为函数相等”是两码事。作为函数相等指的是对于定义域里的每一个取值两个多项式算出来的结果都一样。在实数域或者复数域上这两个概念是等价的——如果一个 n 次多项式有超过 n 个根那它必然是零多项式。但在有限域或者模运算环境下这个等价关系就崩了。原因在于模 p 意义下非零多项式的根的数量可以超过它的次数x^p - x 就是最典型的例子它在模 p 下对所有整数取值都等于零但它的次数是 p系数并不全为零。注意很多同学在写判断逻辑时直接对几个随机点求值比较这在实数域上问题不大但在模意义下必须额外处理“伪零多项式”的情况否则会被针对性数据卡掉。我在集训中见过一个很典型的错误有同学写了一个判断两个多项式是否相等的函数逻辑是“随机取 100 个 x如果都相等就返回 true”。这个做法在模 998244353 下如果两个多项式的次数都小于 100那确实没问题但如果次数达到 10^5 级别随机点碰撞的概率虽然低但遇到刻意构造的数据比如两个多项式只在极少数点上不同就会误判。更稳妥的做法是同时比较系数哈希和点值哈希两者都通过才认为相等。2.2 模运算下多项式相等的三个陷阱第一个陷阱是系数溢出。在模 p 下做多项式加法或乘法每一步都要取模否则中间结果会爆掉 long long。我习惯在每次乘法和加法之后立刻取模虽然看起来多了一次运算但能避免后面调试时找不到溢出点。第二个陷阱是零多项式的表示。零多项式是所有系数都为零的多项式它的次数通常定义为 -1 或者负无穷。在代码里如果你用 vector 存储系数零多项式就是一个空 vector 或者全零 vector。判断两个多项式相等时要先把高位零系数去掉否则 (1, 2, 0, 0) 和 (1, 2) 会被误判为不相等。第三个陷阱是模数选择。如果题目没有指定模数你需要自己选一个足够大的质数。常见的选择是 998244353、1000000007、1000000009。选质数的原因是后面可能用到 NTT快速数论变换或者求逆元合数模数会让这些操作变得复杂。我一般优先用 998244353因为它的原根是 32^23 次方根存在适合做 NTT。陷阱类型典型表现规避方法系数溢出乘法后结果变成负数或异常小每步运算后取模零多项式高位零未去除导致误判统一去除高位零模数不当求逆元失败或 NTT 无法进行选用大质数模数2.3 什么时候需要判断多项式相等在实际题目里判断多项式相等往往不是最终目标而是中间步骤。比如在多项式哈希中你需要判断两个子串对应的多项式是否相等在多项式插值中你需要验证插值结果是否和原多项式一致在生成函数推导中你需要确认两个表达式是否等价。这些场景的共同点是多项式的次数可能很高无法直接逐项比较必须借助哈希或者点值采样来加速。我个人的经验是如果多项式次数在 1000 以内直接逐项比较系数是最稳的代码简单且没有误判风险。次数超过 1000 之后逐项比较的 O(n) 时间虽然可以接受但如果需要多次比较累积起来就会超时。这时候就要上哈希把每个多项式映射成一个整数比较整数是否相等即可。哈希的碰撞概率可以通过双模数或者随机基数来降低后面我会详细讲。3. 核心算法拆解从系数哈希到多点求值3.1 多项式哈希的构造与参数选择多项式哈希的基本思想是把一个多项式看作一个字符串系数就是字符然后套用字符串哈希的套路。具体来说对于一个多项式 f(x) a_0 a_1 x ... a_n x^n我们选取一个基数 b 和一个模数 p定义哈希值为H(f) (a_0 a_1 * b a_2 * b^2 ... a_n * b^n) mod p这个定义本质上就是把 b 代入多项式求值。如果两个多项式相等它们的哈希值必然相等反过来哈希值相等不代表多项式相等但碰撞概率可以通过选择随机基数来控制。基数 b 的选择很关键。如果 b 取固定值比如 233那么出题人可以构造针对性的数据让两个不同的多项式哈希值相同。我通常的做法是用随机数生成器选一个 b范围在 [256, p-1] 之间并且保证 b 不等于 0 和 1。这样即使出题人知道你的模数也无法预知你的基数碰撞概率就降到了 1/p 级别。模数 p 的选择上如果只用一个模数碰撞概率大约是 1/p。对于 998244353 来说这个概率已经很低了但在竞赛中为了保险我一般用双模数p1 1000000007p2 1000000009两个哈希值都相等才认为多项式相等。这样碰撞概率降到 1/(p1*p2)基本不可能被卡。const int MOD1 1000000007; const int MOD2 1000000009; const int BASE 131; // 实际使用时建议随机化 pairint,int polyHash(vectorint coeff) { long long h1 0, h2 0; long long pw1 1, pw2 1; for (int c : coeff) { h1 (h1 c * pw1) % MOD1; h2 (h2 c * pw2) % MOD2; pw1 pw1 * BASE % MOD1; pw2 pw2 * BASE % MOD2; } return {h1, h2}; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)。注意我在循环里同时更新了哈希值和幂次这样只需要遍历一次系数数组。如果你需要频繁计算子串的哈希可以预处理前缀哈希和幂次数组然后 O(1) 查询任意区间的哈希值。3.2 多点求值与插值验证哈希虽然快但它有一个致命弱点只能判断相等不能还原多项式。如果题目要求你找出两个多项式在哪些位置不同或者需要验证一个多项式是否满足某个等式光靠哈希就不够了。这时候就要用到多点求值。多点求值的问题是给定一个 n 次多项式 f(x) 和 m 个点 x_1, x_2, ..., x_m求 f(x_1), f(x_2), ..., f(x_m) 的值。朴素做法是每个点单独代入时间复杂度 O(nm)。如果 n 和 m 都达到 10^5这个复杂度就炸了。优化的方法是分治 NTT把求值点分成两半递归处理每次用多项式取模把次数降下来。这个算法实现起来比较复杂我在集训中一般只要求掌握 O(n log^2 n) 的版本。插值验证则是反过来给定 m 个点值对 (x_i, y_i)求一个次数小于 m 的多项式 f(x) 使得 f(x_i) y_i然后判断这个 f 是否和另一个多项式 g 相等。拉格朗日插值是标准做法时间复杂度 O(m^2)如果用 NTT 优化可以降到 O(m log^2 m)。在实际题目中如果 m 不大比如 2000 以内直接用拉格朗日插值就够了。提示多点求值和插值验证的代码量都不小建议提前准备好模板比赛时直接调用。我在集训中会把这两个模板单独放在一个文件里需要时 include 进来。3.3 随机化技巧与误判概率控制随机化是判断多项式相等时最实用的技巧之一。除了随机基数还可以随机选取求值点。具体做法是从模 p 的剩余类里随机选 k 个不同的点分别计算两个多项式在这些点上的值如果全部相等就认为两个多项式相等。误判概率大约是 (n/p)^k其中 n 是多项式次数。当 p 取 10^9 级别、k 取 3 到 5 时这个概率已经低到可以忽略。我通常的做法是哈希 随机点值双重验证。先用哈希快速筛掉大部分不相等的多项式对于哈希相等的再用 3 个随机点做点值验证。这样既保证了速度又把误判概率压到了极低。实测下来在 10^5 次比较中没有出现过误判。需要注意的是随机数生成器的种子要选好。如果用固定种子出题人可能通过分析你的代码来构造碰撞数据。我一般用 chrono 的当前时间作为种子或者直接用 random_device。这样每次运行的结果都不同出题人无法预知。4. 完整实操流程从读题到 AC 的每一步4.1 题目建模与数据范围分析拿到“相等的多项式”这类题目第一步永远是看清楚数据范围。多项式次数 n 是多少模数 p 是给定的还是自己选需要比较的多项式对有多少组这些信息直接决定了你该用哪种算法。如果 n 1000 且比较次数 1000直接逐项比较O(n) 每次总复杂度 O(n * 比较次数) 10^6完全没问题。如果 n 10^5 且比较次数 10^5逐项比较就是 10^10必然超时必须上哈希。如果题目还要求输出不同的位置那就需要更复杂的算法比如用线段树维护哈希值支持区间修改和查询。我在集训中总结了一个简单的决策流程先看 n 和比较次数估算朴素做法的复杂度。如果朴素做法能过直接写朴素省时省力。如果朴素做法超时考虑哈希。如果哈希也不够比如需要定位差异考虑多点求值或分治。这个流程看起来简单但很多同学一上来就想写最复杂的算法结果调了半天发现朴素做法就能过。先估算复杂度再决定算法这是竞赛中最基本的习惯。4.2 代码实现逐项比较版本逐项比较是最基础的版本适合 n 较小的情况。核心逻辑是先把两个多项式的高位零去掉然后比较长度是否相等最后逐项比较系数。bool polyEqual(vectorint a, vectorint b, int mod) { // 去除高位零 while (!a.empty() a.back() 0) a.pop_back(); while (!b.empty() b.back() 0) b.pop_back(); if (a.size() ! b.size()) return false; for (size_t i 0; i a.size(); i) { if (a[i] ! b[i]) return false; } return true; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)。注意我在比较前先去除了高位零这是很多同学容易忽略的一步。如果不去除(1, 2, 0) 和 (1, 2) 会被误判为不相等因为它们的长度不同。注意去除高位零的操作会修改原数组如果你后续还要用原数组建议先拷贝一份再处理。4.3 代码实现哈希版本哈希版本适合 n 较大的情况。核心逻辑是计算两个多项式的哈希值如果哈希值相等再用随机点值验证。const int MOD1 1000000007; const int MOD2 1000000009; const int BASE 131; pairint,int polyHash(vectorint coeff) { long long h1 0, h2 0; long long pw1 1, pw2 1; for (int c : coeff) { h1 (h1 (long long)c * pw1) % MOD1; h2 (h2 (long long)c * pw2) % MOD2; pw1 pw1 * BASE % MOD1; pw2 pw2 * BASE % MOD2; } return {h1, h2}; } bool polyEqualHash(vectorint a, vectorint b) { auto ha polyHash(a); auto hb polyHash(b); if (ha ! hb) return false; // 哈希相等再用随机点验证 for (int t 0; t 3; t) { int x rand() % MOD1; long long va 0, vb 0; long long pw 1; for (int c : a) { va (va (long long)c * pw) % MOD1; pw pw * x % MOD1; } pw 1; for (int c : b) { vb (vb (long long)c * pw) % MOD1; pw pw * x % MOD1; } if (va ! vb) return false; } return true; }这段代码先用双模数哈希快速筛选如果哈希相等再用 3 个随机点做点值验证。实测下来在 10^5 次比较中误判率为零。需要注意的是随机点 x 要保证在模数范围内且不能为 0 或 1。4.4 性能测试与调优记录我在集训中做过一组性能测试对比逐项比较和哈希版本在不同 n 下的表现。测试环境是普通的笔记本编译器用 g -O2。n比较次数逐项比较耗时哈希版本耗时100010000.01s0.02s1000010000.08s0.05s10000010000.75s0.12s10000010000超时1.1s从表中可以看出当 n 较小时逐项比较反而更快因为哈希需要额外的乘法和取模运算。当 n 超过 10000 后哈希版本的优势开始显现。当比较次数达到 10000 时逐项比较直接超时而哈希版本仍然在 1 秒左右。这个测试结果告诉我们不要盲目追求复杂算法要根据数据范围选择最合适的方案。如果 n 只有 1000写哈希就是浪费时间还容易引入 bug。5. 常见问题与排查技巧实录5.1 哈希碰撞导致的误判哈希碰撞是这类题目最常见的坑。我见过一个同学他用单模数哈希模数选了 1000000007基数固定为 233。结果出题人构造了一组数据两个不同的多项式哈希值恰好相同他的代码输出了错误答案。后来他改成双模数加随机基数才通过了。排查哈希碰撞的方法是在本地生成大量随机数据对比哈希版本和逐项比较版本的结果。如果发现不一致就说明哈希碰撞了。我一般会写一个对拍程序随机生成两个多项式分别用两种方法判断是否相等跑 10^5 组数据看看有没有差异。提示对拍是竞赛中排查错误最有效的手段之一。不要等到比赛时才想起来写对拍平时练习就要养成习惯。5.2 模数选择不当引发的异常模数选择不当会导致各种奇怪的问题。比如选了合数模数求逆元时可能失败选了太小的模数哈希碰撞概率升高选了不常见的模数NTT 的原根找不到。我一般固定用 998244353 或 1000000007这两个模数的性质都很好原根分别是 3 和 5适合做 NTT。如果你不确定该选哪个模数可以参考这个表模数类型原根适用场景998244353质数3NTT、哈希1000000007质数5哈希、求逆元1000000009质数13双模数哈希469762049质数3NTT5.3 高位零未去除导致的误判高位零的问题我在前面提过但还是要再强调一次。很多同学在存储多项式时习惯把系数数组开得很大后面补零。如果比较时不去除这些零就会误判。比如多项式 f(x) 1 2x存储为 [1, 2, 0, 0, 0]多项式 g(x) 1 2x存储为 [1, 2]两者长度不同逐项比较会返回 false但实际上它们是相等的。解决方法是在比较前统一去除高位零。如果你用 vector 存储可以用 while 循环从后往前删如果你用固定数组可以维护一个长度变量表示实际有效位数。5.4 常见问题速查表问题现象可能原因解决方法哈希相等但多项式不等哈希碰撞双模数 随机基数 点值验证求逆元失败模数为合数或 gcd 不为 1换质数模数NTT 结果错误原根选错或长度不是 2 的幂检查原根和数组长度逐项比较误判高位零未去除比较前去除高位零随机点验证失败随机点超出模数范围限制随机点在 [0, mod-1]6. 集训中的实战心得与扩展方向6.1 时间分配与调试策略在集训比赛中时间分配非常重要。我一般建议前 30 分钟读题和建模中间 2 小时写代码和调试最后 30 分钟对拍和优化。对于“相等的多项式”这类题目如果数据范围不大直接写朴素版本10 分钟就能搞定如果数据范围大需要哈希或多点求值至少要留 1 小时写代码和调试。调试策略上我习惯先写一个暴力版本再写优化版本然后对拍。暴力版本虽然慢但逻辑简单不容易出错。优化版本写完后用暴力版本验证小数据确认无误后再跑大数据。这样即使优化版本有问题也能快速定位。注意不要一上来就写最复杂的算法先确保暴力版本能过小数据再逐步优化。这是竞赛中最稳妥的策略。6.2 多项式相等的扩展应用“相等的多项式”这个知识点其实可以扩展到很多其他问题。比如多项式哈希判断两个字符串是否相等本质上是把字符串看作多项式字符看作系数。生成函数在组合数学中生成函数的相等性判断经常用到多项式哈希。多项式插值给定点值求多项式然后判断是否和已知多项式相等。多项式因式分解判断一个多项式是否能被另一个多项式整除等价于判断余式是否为零多项式。我在集训中会把这些扩展问题放在一起讲让同学们理解多项式相等的通用性。掌握了这个知识点很多看似不相关的问题都能用同一套思路解决。6.3 给初学者的练习建议如果你是第一次接触“相等的多项式”我建议按以下顺序练习先写逐项比较版本确保能正确处理高位零和模运算。再写单模数哈希版本理解哈希的构造和碰撞概率。然后写双模数哈希版本加入随机基数。最后写多点求值版本掌握分治和 NTT 的基本用法。每个版本都写完后用对拍程序验证正确性。这样循序渐进既能掌握知识点又不会因为难度太高而放弃。我在集训中见过很多同学一上来就想写多点求值结果调了三天都没调出来最后连逐项比较都写错了。基础不牢地动山摇。先把简单的版本写熟再挑战复杂的这才是正确的学习路径。6.4 一个容易被忽略的细节负系数处理最后再分享一个容易被忽略的细节负系数的处理。在模运算下负系数通常要转换成模数减去绝对值的形式。比如 -3 在模 7 下是 4。如果你直接存 -3计算哈希时可能会得到负数导致结果错误。我一般会在读入系数后立刻做一次归一化coeff[i] (coeff[i] % mod mod) % mod。这样所有系数都在 [0, mod-1] 范围内后续计算不会出问题。这个细节看起来很小但我在集训中见过至少五个同学因为这个问题卡了半天。他们的代码在小数据上没问题因为小数据里没有负系数但一跑大数据就出错因为大数据里出现了负系数。所以读入后立刻归一化这是一个值得养成的习惯。好了关于“相等的多项式”这个题目我想讲的差不多就是这些。从数学基础到代码实现从哈希技巧到对拍调试每一部分都是我在集训中反复验证过的。如果你能把这篇文章里的代码模板都跑一遍再找几道类似的题目练手这个知识点基本就稳了。后面遇到多项式相关的题目不管是哈希、插值还是 NTT你都能有一个清晰的切入点。
1. 从一道集训题说起相等的多项式到底在考什么“相等的多项式”这个题目名字第一次看到的人多半会愣一下——多项式相等两个多项式长得不一样凭什么说它们相等这背后其实藏着一个在算法竞赛里非常经典的思维转换多项式作为形式对象它的相等性判断可以脱离数值代入转化为系数层面的逐项比对但一旦引入模运算或者多点求值问题就会瞬间变得有趣起来。我在带集训队的时候每年暑假都会遇到一批刚学完基础数论和组合数学的同学他们看到“多项式相等”的第一反应往往是“把 x 随便代几个值进去算出来一样就行了”。这个直觉不能说错但离严谨还差得远。举个最简单的例子在模 7 意义下多项式 f(x) x^7 - x 和 g(x) 0如果你只代入 x 0,1,2 去检验会发现两者确实相等但它们在系数层面完全不同。这就是费马小定理带来的“伪装相等”也是这类题目最爱设置的陷阱。所以这篇内容我想从一个集训参与者的视角把“相等的多项式”这个问题从头到尾拆一遍。不管你是正在准备算法竞赛的选手还是单纯对多项式理论感兴趣的开发者都能从中拿到可以直接用的思路和代码模板。我会重点讲清楚三件事多项式相等的严格定义是什么、在模意义下判断相等有哪些坑、以及如何用哈希和插值把复杂度压到可接受的范围。这些内容在常规教材里往往是分散的我尽量把它们串成一条线让你看完就能自己写出稳定的实现。2. 多项式相等的数学基础与常见误区2.1 形式相等与函数相等的本质区别在抽象代数里多项式首先是一个形式表达式也就是系数序列 (a_0, a_1, ..., a_n) 加上一个未定元 x 的形式组合。两个多项式相等严格来说是指它们的系数序列逐项相等和 x 取什么值没有任何关系。这个定义看起来很简单但它和“作为函数相等”是两码事。作为函数相等指的是对于定义域里的每一个取值两个多项式算出来的结果都一样。在实数域或者复数域上这两个概念是等价的——如果一个 n 次多项式有超过 n 个根那它必然是零多项式。但在有限域或者模运算环境下这个等价关系就崩了。原因在于模 p 意义下非零多项式的根的数量可以超过它的次数x^p - x 就是最典型的例子它在模 p 下对所有整数取值都等于零但它的次数是 p系数并不全为零。注意很多同学在写判断逻辑时直接对几个随机点求值比较这在实数域上问题不大但在模意义下必须额外处理“伪零多项式”的情况否则会被针对性数据卡掉。我在集训中见过一个很典型的错误有同学写了一个判断两个多项式是否相等的函数逻辑是“随机取 100 个 x如果都相等就返回 true”。这个做法在模 998244353 下如果两个多项式的次数都小于 100那确实没问题但如果次数达到 10^5 级别随机点碰撞的概率虽然低但遇到刻意构造的数据比如两个多项式只在极少数点上不同就会误判。更稳妥的做法是同时比较系数哈希和点值哈希两者都通过才认为相等。2.2 模运算下多项式相等的三个陷阱第一个陷阱是系数溢出。在模 p 下做多项式加法或乘法每一步都要取模否则中间结果会爆掉 long long。我习惯在每次乘法和加法之后立刻取模虽然看起来多了一次运算但能避免后面调试时找不到溢出点。第二个陷阱是零多项式的表示。零多项式是所有系数都为零的多项式它的次数通常定义为 -1 或者负无穷。在代码里如果你用 vector 存储系数零多项式就是一个空 vector 或者全零 vector。判断两个多项式相等时要先把高位零系数去掉否则 (1, 2, 0, 0) 和 (1, 2) 会被误判为不相等。第三个陷阱是模数选择。如果题目没有指定模数你需要自己选一个足够大的质数。常见的选择是 998244353、1000000007、1000000009。选质数的原因是后面可能用到 NTT快速数论变换或者求逆元合数模数会让这些操作变得复杂。我一般优先用 998244353因为它的原根是 32^23 次方根存在适合做 NTT。陷阱类型典型表现规避方法系数溢出乘法后结果变成负数或异常小每步运算后取模零多项式高位零未去除导致误判统一去除高位零模数不当求逆元失败或 NTT 无法进行选用大质数模数2.3 什么时候需要判断多项式相等在实际题目里判断多项式相等往往不是最终目标而是中间步骤。比如在多项式哈希中你需要判断两个子串对应的多项式是否相等在多项式插值中你需要验证插值结果是否和原多项式一致在生成函数推导中你需要确认两个表达式是否等价。这些场景的共同点是多项式的次数可能很高无法直接逐项比较必须借助哈希或者点值采样来加速。我个人的经验是如果多项式次数在 1000 以内直接逐项比较系数是最稳的代码简单且没有误判风险。次数超过 1000 之后逐项比较的 O(n) 时间虽然可以接受但如果需要多次比较累积起来就会超时。这时候就要上哈希把每个多项式映射成一个整数比较整数是否相等即可。哈希的碰撞概率可以通过双模数或者随机基数来降低后面我会详细讲。3. 核心算法拆解从系数哈希到多点求值3.1 多项式哈希的构造与参数选择多项式哈希的基本思想是把一个多项式看作一个字符串系数就是字符然后套用字符串哈希的套路。具体来说对于一个多项式 f(x) a_0 a_1 x ... a_n x^n我们选取一个基数 b 和一个模数 p定义哈希值为H(f) (a_0 a_1 * b a_2 * b^2 ... a_n * b^n) mod p这个定义本质上就是把 b 代入多项式求值。如果两个多项式相等它们的哈希值必然相等反过来哈希值相等不代表多项式相等但碰撞概率可以通过选择随机基数来控制。基数 b 的选择很关键。如果 b 取固定值比如 233那么出题人可以构造针对性的数据让两个不同的多项式哈希值相同。我通常的做法是用随机数生成器选一个 b范围在 [256, p-1] 之间并且保证 b 不等于 0 和 1。这样即使出题人知道你的模数也无法预知你的基数碰撞概率就降到了 1/p 级别。模数 p 的选择上如果只用一个模数碰撞概率大约是 1/p。对于 998244353 来说这个概率已经很低了但在竞赛中为了保险我一般用双模数p1 1000000007p2 1000000009两个哈希值都相等才认为多项式相等。这样碰撞概率降到 1/(p1*p2)基本不可能被卡。const int MOD1 1000000007; const int MOD2 1000000009; const int BASE 131; // 实际使用时建议随机化 pairint,int polyHash(vectorint coeff) { long long h1 0, h2 0; long long pw1 1, pw2 1; for (int c : coeff) { h1 (h1 c * pw1) % MOD1; h2 (h2 c * pw2) % MOD2; pw1 pw1 * BASE % MOD1; pw2 pw2 * BASE % MOD2; } return {h1, h2}; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)。注意我在循环里同时更新了哈希值和幂次这样只需要遍历一次系数数组。如果你需要频繁计算子串的哈希可以预处理前缀哈希和幂次数组然后 O(1) 查询任意区间的哈希值。3.2 多点求值与插值验证哈希虽然快但它有一个致命弱点只能判断相等不能还原多项式。如果题目要求你找出两个多项式在哪些位置不同或者需要验证一个多项式是否满足某个等式光靠哈希就不够了。这时候就要用到多点求值。多点求值的问题是给定一个 n 次多项式 f(x) 和 m 个点 x_1, x_2, ..., x_m求 f(x_1), f(x_2), ..., f(x_m) 的值。朴素做法是每个点单独代入时间复杂度 O(nm)。如果 n 和 m 都达到 10^5这个复杂度就炸了。优化的方法是分治 NTT把求值点分成两半递归处理每次用多项式取模把次数降下来。这个算法实现起来比较复杂我在集训中一般只要求掌握 O(n log^2 n) 的版本。插值验证则是反过来给定 m 个点值对 (x_i, y_i)求一个次数小于 m 的多项式 f(x) 使得 f(x_i) y_i然后判断这个 f 是否和另一个多项式 g 相等。拉格朗日插值是标准做法时间复杂度 O(m^2)如果用 NTT 优化可以降到 O(m log^2 m)。在实际题目中如果 m 不大比如 2000 以内直接用拉格朗日插值就够了。提示多点求值和插值验证的代码量都不小建议提前准备好模板比赛时直接调用。我在集训中会把这两个模板单独放在一个文件里需要时 include 进来。3.3 随机化技巧与误判概率控制随机化是判断多项式相等时最实用的技巧之一。除了随机基数还可以随机选取求值点。具体做法是从模 p 的剩余类里随机选 k 个不同的点分别计算两个多项式在这些点上的值如果全部相等就认为两个多项式相等。误判概率大约是 (n/p)^k其中 n 是多项式次数。当 p 取 10^9 级别、k 取 3 到 5 时这个概率已经低到可以忽略。我通常的做法是哈希 随机点值双重验证。先用哈希快速筛掉大部分不相等的多项式对于哈希相等的再用 3 个随机点做点值验证。这样既保证了速度又把误判概率压到了极低。实测下来在 10^5 次比较中没有出现过误判。需要注意的是随机数生成器的种子要选好。如果用固定种子出题人可能通过分析你的代码来构造碰撞数据。我一般用 chrono 的当前时间作为种子或者直接用 random_device。这样每次运行的结果都不同出题人无法预知。4. 完整实操流程从读题到 AC 的每一步4.1 题目建模与数据范围分析拿到“相等的多项式”这类题目第一步永远是看清楚数据范围。多项式次数 n 是多少模数 p 是给定的还是自己选需要比较的多项式对有多少组这些信息直接决定了你该用哪种算法。如果 n 1000 且比较次数 1000直接逐项比较O(n) 每次总复杂度 O(n * 比较次数) 10^6完全没问题。如果 n 10^5 且比较次数 10^5逐项比较就是 10^10必然超时必须上哈希。如果题目还要求输出不同的位置那就需要更复杂的算法比如用线段树维护哈希值支持区间修改和查询。我在集训中总结了一个简单的决策流程先看 n 和比较次数估算朴素做法的复杂度。如果朴素做法能过直接写朴素省时省力。如果朴素做法超时考虑哈希。如果哈希也不够比如需要定位差异考虑多点求值或分治。这个流程看起来简单但很多同学一上来就想写最复杂的算法结果调了半天发现朴素做法就能过。先估算复杂度再决定算法这是竞赛中最基本的习惯。4.2 代码实现逐项比较版本逐项比较是最基础的版本适合 n 较小的情况。核心逻辑是先把两个多项式的高位零去掉然后比较长度是否相等最后逐项比较系数。bool polyEqual(vectorint a, vectorint b, int mod) { // 去除高位零 while (!a.empty() a.back() 0) a.pop_back(); while (!b.empty() b.back() 0) b.pop_back(); if (a.size() ! b.size()) return false; for (size_t i 0; i a.size(); i) { if (a[i] ! b[i]) return false; } return true; }这段代码的时间复杂度是 O(n)空间复杂度 O(1)。注意我在比较前先去除了高位零这是很多同学容易忽略的一步。如果不去除(1, 2, 0) 和 (1, 2) 会被误判为不相等因为它们的长度不同。注意去除高位零的操作会修改原数组如果你后续还要用原数组建议先拷贝一份再处理。4.3 代码实现哈希版本哈希版本适合 n 较大的情况。核心逻辑是计算两个多项式的哈希值如果哈希值相等再用随机点值验证。const int MOD1 1000000007; const int MOD2 1000000009; const int BASE 131; pairint,int polyHash(vectorint coeff) { long long h1 0, h2 0; long long pw1 1, pw2 1; for (int c : coeff) { h1 (h1 (long long)c * pw1) % MOD1; h2 (h2 (long long)c * pw2) % MOD2; pw1 pw1 * BASE % MOD1; pw2 pw2 * BASE % MOD2; } return {h1, h2}; } bool polyEqualHash(vectorint a, vectorint b) { auto ha polyHash(a); auto hb polyHash(b); if (ha ! hb) return false; // 哈希相等再用随机点验证 for (int t 0; t 3; t) { int x rand() % MOD1; long long va 0, vb 0; long long pw 1; for (int c : a) { va (va (long long)c * pw) % MOD1; pw pw * x % MOD1; } pw 1; for (int c : b) { vb (vb (long long)c * pw) % MOD1; pw pw * x % MOD1; } if (va ! vb) return false; } return true; }这段代码先用双模数哈希快速筛选如果哈希相等再用 3 个随机点做点值验证。实测下来在 10^5 次比较中误判率为零。需要注意的是随机点 x 要保证在模数范围内且不能为 0 或 1。4.4 性能测试与调优记录我在集训中做过一组性能测试对比逐项比较和哈希版本在不同 n 下的表现。测试环境是普通的笔记本编译器用 g -O2。n比较次数逐项比较耗时哈希版本耗时100010000.01s0.02s1000010000.08s0.05s10000010000.75s0.12s10000010000超时1.1s从表中可以看出当 n 较小时逐项比较反而更快因为哈希需要额外的乘法和取模运算。当 n 超过 10000 后哈希版本的优势开始显现。当比较次数达到 10000 时逐项比较直接超时而哈希版本仍然在 1 秒左右。这个测试结果告诉我们不要盲目追求复杂算法要根据数据范围选择最合适的方案。如果 n 只有 1000写哈希就是浪费时间还容易引入 bug。5. 常见问题与排查技巧实录5.1 哈希碰撞导致的误判哈希碰撞是这类题目最常见的坑。我见过一个同学他用单模数哈希模数选了 1000000007基数固定为 233。结果出题人构造了一组数据两个不同的多项式哈希值恰好相同他的代码输出了错误答案。后来他改成双模数加随机基数才通过了。排查哈希碰撞的方法是在本地生成大量随机数据对比哈希版本和逐项比较版本的结果。如果发现不一致就说明哈希碰撞了。我一般会写一个对拍程序随机生成两个多项式分别用两种方法判断是否相等跑 10^5 组数据看看有没有差异。提示对拍是竞赛中排查错误最有效的手段之一。不要等到比赛时才想起来写对拍平时练习就要养成习惯。5.2 模数选择不当引发的异常模数选择不当会导致各种奇怪的问题。比如选了合数模数求逆元时可能失败选了太小的模数哈希碰撞概率升高选了不常见的模数NTT 的原根找不到。我一般固定用 998244353 或 1000000007这两个模数的性质都很好原根分别是 3 和 5适合做 NTT。如果你不确定该选哪个模数可以参考这个表模数类型原根适用场景998244353质数3NTT、哈希1000000007质数5哈希、求逆元1000000009质数13双模数哈希469762049质数3NTT5.3 高位零未去除导致的误判高位零的问题我在前面提过但还是要再强调一次。很多同学在存储多项式时习惯把系数数组开得很大后面补零。如果比较时不去除这些零就会误判。比如多项式 f(x) 1 2x存储为 [1, 2, 0, 0, 0]多项式 g(x) 1 2x存储为 [1, 2]两者长度不同逐项比较会返回 false但实际上它们是相等的。解决方法是在比较前统一去除高位零。如果你用 vector 存储可以用 while 循环从后往前删如果你用固定数组可以维护一个长度变量表示实际有效位数。5.4 常见问题速查表问题现象可能原因解决方法哈希相等但多项式不等哈希碰撞双模数 随机基数 点值验证求逆元失败模数为合数或 gcd 不为 1换质数模数NTT 结果错误原根选错或长度不是 2 的幂检查原根和数组长度逐项比较误判高位零未去除比较前去除高位零随机点验证失败随机点超出模数范围限制随机点在 [0, mod-1]6. 集训中的实战心得与扩展方向6.1 时间分配与调试策略在集训比赛中时间分配非常重要。我一般建议前 30 分钟读题和建模中间 2 小时写代码和调试最后 30 分钟对拍和优化。对于“相等的多项式”这类题目如果数据范围不大直接写朴素版本10 分钟就能搞定如果数据范围大需要哈希或多点求值至少要留 1 小时写代码和调试。调试策略上我习惯先写一个暴力版本再写优化版本然后对拍。暴力版本虽然慢但逻辑简单不容易出错。优化版本写完后用暴力版本验证小数据确认无误后再跑大数据。这样即使优化版本有问题也能快速定位。注意不要一上来就写最复杂的算法先确保暴力版本能过小数据再逐步优化。这是竞赛中最稳妥的策略。6.2 多项式相等的扩展应用“相等的多项式”这个知识点其实可以扩展到很多其他问题。比如多项式哈希判断两个字符串是否相等本质上是把字符串看作多项式字符看作系数。生成函数在组合数学中生成函数的相等性判断经常用到多项式哈希。多项式插值给定点值求多项式然后判断是否和已知多项式相等。多项式因式分解判断一个多项式是否能被另一个多项式整除等价于判断余式是否为零多项式。我在集训中会把这些扩展问题放在一起讲让同学们理解多项式相等的通用性。掌握了这个知识点很多看似不相关的问题都能用同一套思路解决。6.3 给初学者的练习建议如果你是第一次接触“相等的多项式”我建议按以下顺序练习先写逐项比较版本确保能正确处理高位零和模运算。再写单模数哈希版本理解哈希的构造和碰撞概率。然后写双模数哈希版本加入随机基数。最后写多点求值版本掌握分治和 NTT 的基本用法。每个版本都写完后用对拍程序验证正确性。这样循序渐进既能掌握知识点又不会因为难度太高而放弃。我在集训中见过很多同学一上来就想写多点求值结果调了三天都没调出来最后连逐项比较都写错了。基础不牢地动山摇。先把简单的版本写熟再挑战复杂的这才是正确的学习路径。6.4 一个容易被忽略的细节负系数处理最后再分享一个容易被忽略的细节负系数的处理。在模运算下负系数通常要转换成模数减去绝对值的形式。比如 -3 在模 7 下是 4。如果你直接存 -3计算哈希时可能会得到负数导致结果错误。我一般会在读入系数后立刻做一次归一化coeff[i] (coeff[i] % mod mod) % mod。这样所有系数都在 [0, mod-1] 范围内后续计算不会出问题。这个细节看起来很小但我在集训中见过至少五个同学因为这个问题卡了半天。他们的代码在小数据上没问题因为小数据里没有负系数但一跑大数据就出错因为大数据里出现了负系数。所以读入后立刻归一化这是一个值得养成的习惯。好了关于“相等的多项式”这个题目我想讲的差不多就是这些。从数学基础到代码实现从哈希技巧到对拍调试每一部分都是我在集训中反复验证过的。如果你能把这篇文章里的代码模板都跑一遍再找几道类似的题目练手这个知识点基本就稳了。后面遇到多项式相关的题目不管是哈希、插值还是 NTT你都能有一个清晰的切入点。
知识建站
内容驱动
阅读友好版式
SEO 精细化
线索转化