ビット演算を用いた非再帰 FFT離散フーリエ変換（ DFT ）の定義 n 個の複素数列 \bm{x} = (x_0, x_1, \ldots, x_{n - 1}) に対し，これらの離散フーリエ変換（ DFT ） \bm{X} = (X_0, X_1, \ldots, X_{n - 1}) は次で定義されます． X_k = \sum_{j = 0}^{n - 1} \zeta_n^{-jk} x_j \tag{1} ただし \zeta_n は \zeta_n = e^{\frac{2\pi i}{n}} = \cos\frac{2\pi}{n} + i\sin\frac{2\pi}{n} で定義され， n 乗すると 1 になる虚数の 1 つです． \zeta_{2n} の 2a 乗を計算すると， \zeta_{2n}^{2a} = e^{\frac{2\pi i}{2n}\cdot 2a} = e^{\frac{2\pi
RustCoder ―― AtCoder と Rust で始める競技プログラミング入門
