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

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

## 保持差的方向

设某个单位根处的值为 $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 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.277414 秒，补充方案为 0.843589 秒；峰值工作集分别为 7.31 与 7.62 MiB，包含进程与运行库开销。
补充程序在全部已测正式输入上均低于 1.0 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。