競プロのための高速フーリエ変換■「フーリエ変換って知ってる？」 ●「フーリエ変換ですか？ 信号処理でもするんですか、先輩」 ■「いや、競プロで使えるようになりたいなって」 ●「ああ、畳み込みの高速化ですか。あれは高速フーリエ変換をそのまま使うだけですからね」 ■「勉強しようと思って色々調べたんだけど、なかなか理解できなくて」 ●「私もうまく説明できるかわかりませんが、お話しましょうか」 離散フーリエ変換（DFT） フーリエ変換の仲間たち ●「フーリエ変換の仲間には色々種類があるんですけど、競プロで使うのは離散フーリエ変換（DFT: Discrete Fourier Transform）ですね」 ■「離散ってことは、連続もあるんだよね」 ●「はい。ざっくり 4 種類あります。フーリエ変換では元の信号を別の信号に変換するんですが、元の信号が周期信号だと変換後は離散信号（数列）になります」 ■「周期信号っていうのは、決まった
