始めに FFTについて、勉強する機会があったため備忘録に記事を書こうと思いました。 問題設定 離散フーリエ変換を高速に行うアルゴリズムです。 しかし、今回は次の問題を考えることにし信号処理的な背景をすべて忘れることにします。 2つの数列$A_0,\ldots,…