FFT入門したメモ
ABC291-Gのupsolveメモです。
ゴール：ACLのconvolutionを用いて典型的なFFTを解けるようにする
#ACLのドキュメント
https://atcoder.github.io/ac-library/document_ja/convolution.html
#FFTの解説
競プロ的にはこれで初級は十分な気がする。
【競プロer向け】FFT を習得しよう！
FFT（高速フーリエ変換）を完全に理解する話
離散フーリエ変換から気持ちを学ぶなら学部向けのディジタル信号処理の教科書とか？
やる夫で学ぶディジタル信号処理
#入門問題
AtCoder Typical Contest 001 C - 高速フーリエ変換
スライドが丁寧。
#典型問題（ABC黄diff）
ABC196 F Substring 2
左右反転する典型
ABC291 G - OR Sum
掛け算に直す典型