FFT
概要
離散フーリエ変換という処理を高速に行うアルゴリズムのこと。
これを利用して、多項式乗算が高速に行える。
例えば
i円の主菜がA[i]種類、j円の副菜がB[j]種類あるとき、主菜と副菜とを1つずつ組み合わせてちょうどk円になる組み合わせはいくつあるか？
普通なら、主菜がN種類、副菜がN種類あるとすると、O(n^2) かかってしまう。これをO(n logn)で解く。
実装
code:c++
vector<int> p(1000005);
// ...略... pに値を代入
auto c = convolution(p,p);
// ここで c10 などに畳み込みの結果が入っている 参考
問題例