令 \(f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\)．
\[\begin{bmatrix}
a_0 & a_1 & \cdots & a_{n-1}\\
a_{n-1} & a_0 & \cdots & a_{n-2}\\
\vdots & \vdots & \ddots & \vdots\\
a_1 & a_2 & \cdots & a_0
\end{bmatrix}
\begin{bmatrix}
1 & 1 & \cdots & 1\\
1 & \omega_n^1 & \cdots & \omega_n^{n-1}\\
\vdots & \vdots & \ddots & \vdots\\
1 & \omega_n^{n-1} & \cdots & \omega_n^{(n-1)^2}
\end{bmatrix}
=
\begin{bmatrix}
1f(1) & 1f(\omega_n^1) & \cdots & 1f(\omega_n^{n-1})\\
1f(1) & \omega_n^1f(\omega_n^1) & \cdots & \omega_n^{n-1}f(\omega_n^{n-1})\\
\vdots & \vdots & \ddots & \vdots\\
1f(1) & \omega_n^{n-1}f(\omega_n^1) & \cdots & \omega_n^{(n-1)^2}f(\omega_n^{n-1})
\end{bmatrix}
\]
也就是将要求行列式的矩阵 \(A\) 乘上 dft 的那个范德蒙德矩阵 \(B\)．
左右两边行列式：
\(LHS=\det(AB)=\det(A)\det(B)\)
\(RHS=\prod\limits_{i=0}^{n-1}f(\omega_n^i)\det(B)\)
而 \(\det(B)=\prod_{0\leq j<i<n}(\omega_n^i-\omega_n^j)\)，由于 \(n\) 次单位根两两不同，这个值不为 \(0\)，所以可以两边同时约去。
那我们所求的就是 \(\prod\limits_{i=0}^{n-1}f(\omega_n^i)\)．
需要 Bluestein's Algorithm，这我还不会。