読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.206

yukicoder

FFT多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね…

情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので,今回はFFTの実装がメイン.バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれど,やっていることはただの再帰ですね.改めてdft(離散フーリエ変換)とidft(逆変換)の対応がわかってよかった.

いざ実戦で使うとなると,1から書くにはデバッグ時間を取られすぎるので,ライブラリ化しておきたい.

 

yukicoder No.206