この記事は Competitive Programming Advent Calendar 2017 の24日目の記事です。 はじめに この記事の内容 この記事では FFT のアルゴリズムの中身は説明しません。 競プロの問題を解く上で知っておくと有利になりそな部分だけ解説します。 「2つの配列を畳み込むアルゴリズム」として解釈してると 困るかもしれませんという内容です。そう思ってない人には 当り前のことしか書いてありません。 畳み込みとは 数列 と に対して、 で定義される数列 を求める操作を 畳み込みと呼びます。 それぞれの数列を係数として持つ多項式 , , を考えると、 となっているので、 畳み込みのかわりに多項式の積を考えても同じことになります。 準備 突然ですが、 昨日僕が出題した問題を 解いて下さい(脳内ACでもいいです)。 この問題のミソは、 次の多項式の掛け算をするのには か