參考資料 https://oi.men.ci/fft-notes/
機關根(此類群均可)
(ω^0, ω^1, dots, ω^{n-1}互不相同)
(ω^k_n=ω^{2k}_{2n})
(ω^{k+n/2}_n = ω^{-k}_n)
(ω_n^n=ω_n^0=1)
DFT
[A =(a_0, a_1,cdots, a_{n-1})\
A(x)=a_0+a_1x+a_2x^2+cdots+a_{n-1}x^{n-1}\
A' = DFT(A) = (A(ω_n^0), cdots, A(ω_n^{n-1}))\
A'是A的DFT.
]
[ egin{align*} A_0(x) &= a_0 + a_2 x + a_4 x ^ 2 + dots + a_{n - 2} x ^ {frac{n}{2} - 1} \ A_1(x) &= a_1 + a_3 x + a_5 x ^ 2 + dots + a_{n - 1} x ^ {frac{n}{2} - 1} end{align*} \
.\
有A(ω_n^k) = A_0(ω^k_{n/2})+ω_n^kA_1(ω^k_{n/2}), kin [0, n/2)
\A(ω_n^k) = A_0(ω^k_{n/2})-ω_n^kA_1(ω^k_{n/2}), kin [n/2, n)
]
IDFT
[A =(a_0, a_1,cdots, a_{n-1})\
A(x)=a_0+a_1x+a_2x^2+cdots+a_{n-1}x^{n-1}\
A' = IDFT(A) = (A(ω_n^0)/n,A(omega_n^{-1})/n, cdots, A(ω_n^{-(n-1)})/n)\
A'是A的IDFT.
]
蝶形變換
(00, 01, 10, 11)
先按奇偶性分類
(00, 10), (01, 11)
不考慮末位之後，開始最初奇偶性分類過程
（0，1），（0，1）
是以反轉二進制位，按反轉後順序操作。