线代课本 3.5 节是 FFT，好吧我也来 review 一下...
\(FF^* \to F^2 \to\) 对 DFT 转置 \(\to\) 交换正逆变换
\(F\boldsymbol{a}=(f(\omega^{1}_{n}), f(\omega^{2}_{n}),\cdots,f(\omega^{n}_{n}))^\intercal\)
\((F)_{nn}(F^*)_{nn} = nI\)，其中 \(F^*\) 为 \(F\) 的共轭转置
\(F_n\) 可以方便的由 \(F_{n/2}\) 得到
\(\omega^{2k}_{n}=\omega^{k}_{n/2}\) 提示将列进行奇偶分类
\[ \begin{pmatrix} 1 & 1 & \cdots & 1 \\ 1 & \omega^{1}_{n} & \cdots & \omega^{n-1}_{n} \\ 1 & \omega^{2}_{n} & \cdots & \omega^{2(n-1)}_{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1}_{n} & \cdots & \omega^{(n-1)^2}_{n} \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 1 & \cdots & 1 & 1 & \cdots \\ 1 & \omega^{1}_{n/2} & \cdots & \omega^{0+1}_{n} & \omega^{2+1}_{n} & \cdots \\ 1 & \omega^{2}_{n/2} & \cdots & \omega^{0+2}_{n} & \omega^{4+2}_{n} & \cdots \\ \vdots & \vdots & & \vdots &\\ 1 & \omega^{n-1}_{n/2} & \cdots & \omega^{0+(n-1)}_{n} & \omega^{2(n-1)+(n-1)}_{n} & \cdots \end{pmatrix} \]
左上左下都是 \(F_{n/2}\)，右上右下还要额外在第 \(i\) 行上乘 \(\omega^{i}_{n}\)：
\[ F_{2n}= \begin{pmatrix} I_{n} & D_{n} \\ I_{n} & -D_{n} \end{pmatrix} \begin{pmatrix} F_{512} & \\ & F_{512} \end{pmatrix} P \]
\(D_{n}\) 是将 \(\omega^{i}_{2n} (i\le n)\) 依次排列在对角线上得到的矩阵
不断展开 \(F_{n}\)，右边即对应位反转操作，左边是分治过程
单位根反演还告诉了我们 \(\sum\limits^{n-1}_{i=0} (\omega^{i}_{n})^k=n\) 当且仅当 \(n|k\) 时成立
借此观察 \(F^2\)：
\[ F^2= \begin{pmatrix} n & 0 & \cdots & 0 & 0 \\ 0 & 0 & \cdots & 0 & n \\ 0 & 0 & \cdots & n & 0 \\ \vdots & & \vdots & \vdots & \vdots \\ 0 & n & \cdots & 0 & 0 \end{pmatrix} \]
所以实现时可以统一使用 \(\omega^{i}_{n}\)
若要消去蝴蝶变换，根据 \(F_{2n}\) 的递归式对整个 DFT 使用转置而保留 IDFT 的形式得到朴素的 DIF-DIT
若要将 \(O(n\log n)\) 次原根移动缩减为 \(O(n)\) 次：
观察得应在每个算法的开头进行蝴蝶变换并改变枚举区间大小的次序
而因为对 \(\boldsymbol{a}\) 进行的是 \(F^2\) 故可以继续交换这两个算法，这样交换之后使用的单位根数组应当被蝴蝶变换掉
\(\omega^{i}_{n} = \omega^{2i}_{2n}\)，旧值末位加零反转后首位为零，故长为 \(n\) 的单位根数组经过蝴蝶变换之后总为长为 \(2n\) 的单位根数组的前缀
用一个预处理好的足够大的单位根数组就可以完成所有操作