# Grox的序列七题解

**出题人解法：Vandermonde 行列式、单位根求值与 NTT。** Codex（GPT-6）修复变换的位逆序置换和单位根表实现，规范模数余数，并处理一阶矩阵。算法及主要建模沿用出题人方案。

## 行列式转为差的乘积

令 $N=2^k$ .矩阵的第 $i$ 列为 $1,A_i,A_i^2,\ldots,A_i^{N-1}$ ，是多项式环上的 Vandermonde 矩阵。其行列式为

$$B(x)=\prod_{1\le i<j\le N}(A_j(x)-A_i(x))$$

这个恒等式在任意交换环中成立。可以先视 $A_i$ 为独立变量：交换两列使行列式变号，两个变量相等时它为零，因此每个差都是因子；行列式与差的乘积总次数相同，再比较单项式 $A_2A_3^2\cdots A_N^{N-1}$ 的系数，得到比例常数为 $1$ .随后代入多项式仍成立。

![四列 Vandermonde 矩阵的多项式排列](assets/vandermonde.svg)

图中展示 $N=4$ 时的结构。输入的一行描述一个多项式，而这个多项式的各次幂构成矩阵的一列。

## 指数折叠与单位根

输出等于 $B(x)$ 对 $x^N-1$ 取余，因为 $x^N\equiv1$ ，每个指数折叠到它对 $N$ 的余数。无需展开可能具有很高次数的行列式。

模数 $P=1004535809=479\times2^{21}+1$ 是质数，$3$ 是原根。令

$$\omega=3^{(P-1)/N}\bmod P$$

$1,\omega,\ldots,\omega^{N-1}$ 是 $N$ 个不同的单位根。先对每个输入多项式做长度为 $N$ 的 NTT，得到各单位根处的值。然后逐点计算

$$B(\omega^t)=\prod_{i<j}(A_j(\omega^t)-A_i(\omega^t))$$

最后对这一组值做逆 NTT，恢复次数小于 $N$ 的余式系数。

## 正确性与实现注意

Vandermonde 恒等式把行列式准确写成差的乘积。在单位根处，$x^N-1$ 为零，所以原多项式与余式的求值一致；长度为 $N$ 的 NTT 可逆，因此逆变换唯一恢复所需余式。$N=1$ 时差的乘积为空积，结果为常数 $1$ ，与一阶矩阵一致。

位逆序置换比较的是下标 $i<j$ ，不能比较这两个位置存储的数值。每一层的旋转因子由对应单位根连续相乘生成。逆变换使用逆单位根，再乘以 $N$ 的逆元。差的负余数在乘法前规范。

## 复杂度

$N$ 次输入变换需要 $O(N^2\log N)$ 时间；每个单位根上有 $\binom N2$ 个差，总计 $O(N^3)$ 次乘法；逆变换需 $O(N\log N)$ .总时间 $O(N^3+N^2\log N)$ ，空间 $O(N^2)$ .直接在多项式系数域逐次相乘仍正确，但一次循环卷积的朴素代价为 $O(N^2)$ ，总时间为 $O(N^4)$ ，适合小规模独立验证。

## 补充解法

单位根处的差积可用有序分治、乘积树与多点求值计算，总时间为 $O(N^2(1+\log N)^3)$ ，渐进增长阶低于逐对相乘。小多项式变换和除法的常数更高，当前 $N\le512$ 的实测更慢，但通过全部已测输入的 1.0 秒时限；保留为具有渐进优势的并列算法，标程仍选逐对相乘。

[完整题解与测量](solution-alternative-product-tree.zh.md) · [计算程序](alternative-product-tree.cpp)