Reference：@自为风月马前卒 亦 @attack 的博客
这里为了帮助我自己理解，先手推（抄）一遍这位 dalao 给出的快速傅里叶逆变换的证明。
\((y_0, y_1, \dots, y_{n-1})\) 为多项式 \((a_0, a_1, \dots, a_{n-1})\) 在 \(x\) 取 \((\omega^0_n, \omega^1_n, \dots, \omega^{n-1}_n)\) 时的点值表示（亦称傅里叶变换）。
设有一向量 \((c_0, c_1, \dots, c_{n-1})\) 为 \((y_0, y_1, \dots, y_{n-1})\) 在 \(x\) 取 \((\omega^0_n, \omega^{-1}_n, \dots, \omega^{-(n-1)}_n)\) 时的点值表示。形式化地，它满足：
\[c_k = \sum^{n-1}_{i=0} y_i(w_n^{-k})^i \\= \sum^{n-1}_{i=0} y_i(w_n^{-k})^i \] 标签：dots,多项式,sum,FFT,点值,omega,乘法 From： https://www.cnblogs.com/David-Mercury/p/18157910