2015-09-14 yukicoder No.206 yukicoder FFT.多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね… 情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので,今回はFFTの実装がメイン.バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれど,やっていることはただの再帰ですね.改めてdft(離散フーリエ変換)とidft(逆変換)の対応がわかってよかった. いざ実戦で使うとなると,1から書くにはデバッグ時間を取られすぎるので,ライブラリ化しておきたい. yukicoder No.206