Grox的序列七题解¶
出题人解法：Vandermonde 行列式、单位根求值与 NTT。 Codex（GPT-6）修复变换的位逆序置换和单位根表实现，规范模数余数，并处理一阶矩阵。算法及主要建模沿用出题人方案。
行列式转为差的乘积¶
令 \(N=2^k\) .矩阵的第 \(i\) 列为 \(1,A_i,A_i^2,\ldots,A_i^{N-1}\) ，是多项式环上的 Vandermonde 矩阵。其行列式为
这个恒等式在任意交换环中成立。可以先视 \(A_i\) 为独立变量：交换两列使行列式变号，两个变量相等时它为零，因此每个差都是因子；行列式与差的乘积总次数相同，再比较单项式 \(A_2A_3^2\cdots A_N^{N-1}\) 的系数，得到比例常数为 \(1\) .随后代入多项式仍成立。
图中展示 \(N=4\) 时的结构。输入的一行描述一个多项式，而这个多项式的各次幂构成矩阵的一列。
指数折叠与单位根¶
输出等于 \(B(x)\) 对 \(x^N-1\) 取余，因为 \(x^N\equiv1\) ，每个指数折叠到它对 \(N\) 的余数。无需展开可能具有很高次数的行列式。
模数 \(P=1004535809=479\times2^{21}+1\) 是质数，\(3\) 是原根。令
\(1,\omega,\ldots,\omega^{N-1}\) 是 \(N\) 个不同的单位根。先对每个输入多项式做长度为 \(N\) 的 NTT，得到各单位根处的值。然后逐点计算
最后对这一组值做逆 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 秒时限；保留为具有渐进优势的并列算法，标程仍选逐对相乘。