畳み込み
（線形）畳み込みは、長さ$ Nの数列$ A = (A_0, A_1, \ldots, A_N)と、長さ$ Mの数列$ B = (B_0, B_1, \ldots, B_M)から、長さ$ N + M - 1の数列$ Cを作る演算
ここで、数列$ Cは以下のように表すことができる
$ C_i = \sum_{j = 0}^{i} A_{j} B_{i - j}
畳み込みを普通に計算すると$ O(N^2)だが、FFTやNTTを使うことで$ O(N \log N)で計算できる→FFTの大雑把な説明 畳み込みの用途
多項式の積
FPS
多倍長整数の掛け算
その他
多項式の積
多項式の積は、係数の数列の畳み込みとみなすことができる
多項式$ f(x) = \sum_{i = 0}^{N - 1} a_i x^i, g(x) = \sum_{i = 0}^{M - 1} b_i x^iがあるとき、二つの積$ h(x)は、以下のようになる
$ h(x) = \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_i b_j x^{i + j}
ここで、$ i + j = kと置く
$ h(x) = \sum_{i = 0}^{N - 1} \sum_{k = i}^{i + M - 1} a_i b_{k - i} x^k
添字の範囲を拡張する（添字が範囲外に出た時は$ 0とする）
$ h(x) = \sum_{i = 0}^{N - 1} \sum_{k = 0}^{N + M - 1} a_i b_{k - i} x^k
さらに、Σを入れ替える
$ h(x) = \sum_{k = 0}^{N + M - 1} \sum_{i = 0}^{N} a_i b_{k - i} x^k
$ b_{k - i} = 0 \quad (i > k)なので
$ h(x) = \sum_{k = 0}^{N + M - 1} \sum_{i = 0}^{k} a_i b_{k - i} x^k
内側のΣを$ c_i = \sum_{j = 0}^{i} a_j b_{i - j}と置くと
$ h(x) = \sum_{k = 0}^{N + M - 1} c_k x^k
多倍長整数の掛け算
多倍長整数は多項式とみなすことができる
→多項式の積を使うことで、掛け算を畳み込みで計算できる
TODO 書く