本系列恢复更新了。它将重新阐释之前学过的算法。
快速傅里叶变换在算法竞赛中特指一种\(O(n\log n)\)转换系数表示法和点值表示法的算法。
记\(\omega_n\)为\(n\)次单位根，即\(\omega_n^n=1\)。
单位根有一个良好性质\(\omega_n^{k+\frac n2}=-\omega_n^k\)，可以通过复数的几何意义来证明。
令\((b_0,b_1,b_2,\cdots,b_{n-1})\)是多项式\(A(x)\)的离散傅里叶变换，即将\((\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1})\)代入\(A(x)\)得到的点值表示。
再令\(B(x)=b_0+b_1x+b_2x^2+\cdots+b_{n-1}x^{n-1}\)，将\((\omega_n^0,\omega_n^{-1},\omega_n^{-2},\cdots,\omega_n^{-(n-1)})\)代入：
原文：https://www.cnblogs.com/teafrogsf/p/post-FFT.html