GitHub 源文件 Markdown English

Grox的序列七：乘积树计算差的乘积¶

出题人解法：Vandermonde 恒等式与单位根变换。Codex（GPT-6）：应用乘积树和多点求值计算有序差的乘积。 计算程序保留主题解的外层归约，改变每个求值点上的算法。乘积树、多点求值与多项式逆元都是通用方法。

保持差的方向¶

设某个单位根处的值为 \(v_i=A_i(\omega^t)\) ，需要求

\[ D(v_1,\ldots,v_N)=\prod_{i<j}(v_j-v_i) \]

按原编号把一段分成左右两半。段内差积等于左右段内差积乘以跨段差积。若

\[ F_L(y)=\prod_{i\in L}(y-v_i) \]

则跨段部分是

\[ \prod_{j\in R}F_L(v_j) \]

所有左编号小于右编号，因而每个差恰为右值减左值，不需要开平方或猜测符号。单点段的差积为空积一。

乘积树与余式树¶

先建立整段乘积树，每个节点存放其区间的首一多项式 \(\prod_i(y-v_i)\) ，父节点是子节点多项式的乘积。

在计算跨段部分时，将 \(F_L\) 沿右半区的乘积树下传：传给一个节点之前，先对其多项式取余。取余不改变该节点任一根上的求值；到叶子后即为 \(F_L(v_j)\) .把叶子值相乘，得到跨段部分，再乘两段递归结果。

快速取余使用反转后的多项式除法。若 \(A=BQ+R\) 且 \(\deg R<\deg B\) ，把已知次数补齐后反转，高次项对应的商满足

\[ \operatorname{rev}Q=\operatorname{rev}A\cdot(\operatorname{rev}B)^{-1}\pmod{y^{\deg Q+1}} \]

首一除数反转后的常数项为一，可用 Newton 迭代求逆。反转恢复商，再计算余式。小规模除法直接用高次项消元以减少常数。

正确性与重复值¶

乘积树存储准确的区间根多项式，余式树保持每个叶子上的求值。左右段内积与跨段积把每一对编号恰好分配一次，所以递归结果就是带正确符号的 Vandermonde 差积。外层 NTT 与逆 NTT 的正确性见主题解。

不要求 \(v_i\) 互异：重复值使某个段内积或跨段求值为零，正确产生零行列式。程序只对首一多项式或非零常数项级数求逆，不对点差求逆，因此重复值不会导致非法除法。\(N=1\) 时返回空积一。

复杂度与取舍¶

一个大小为 \(s\) 的跨段多点求值需 \(O(s(1+\log s)^2)\) 时间。将所有递归层相加，每个单位根上的差积需 \(O(N(1+\log N)^3)\) 时间。外层共 \(N\) 个点，包括输入变换后的总时间为

\[ O(N^2(1+\log N)^3) \]

输入占 \(O(N^2)\) 空间，当前乘积树及余式递归占 \(O(N(1+\log N))\) ；总空间为两者之和。

相较逐对相乘的 \(O(N^3)\) 时间，它在渐进意义上降低了增长阶，但多次小多项式变换、除法与内存分配有更大常数。本题 \(N\le512\) ，不能从渐进界推出更快。逐对相乘仍作为首选；乘积树提供另一种算法，实际时限适用性见同输入测量。不改变题面规模来掩盖这项取舍。

同输入测量¶

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见完整记录，环境见参考评测环境。标程最慢中位耗时为 0.277414 秒，补充方案为 0.843589 秒；峰值工作集分别为 7.31 与 7.62 MiB，包含进程与运行库开销。补充程序在全部已测正式输入上均低于 1.0 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。