FFT
説明
らてさんありがとうございます。
計算量
$O(n \log n)$
実装例
応用: NTT
mod 上のFFT。サイズ $n$ の NTT をするとき mod の原始 $n$ 乗根が必要になる。よく使いそうな素数と原始根のペアとして, 周期$2^{21}$ の $(1012924417, 5), (924844033, 5)$ などがある。
頑張れば任意 mod も可能。
応用: 高速ウォルシュアダマール変換
xor, and, or での畳み込み。