畳み込み | Notion

畳み込みの理論

2つの畳み込み
- $(a * b)[k] = \sum_{i + j = k} a[i]\ b[j]$
- $a,b$ は無限数列、または $\mathbb{N}\to R$ の写像だと思う
3つの畳み込み
- $(a * b*c)[l] = \sum_{i + j + k= l} a[i]\ b[j]\ c[k]$
畳み込みの単位元は $(1, 0, 0, \ldots)$
巡回畳み込み
- $a, b\colon \mathbb{Z}/N\mathbb{Z} \to R$ としたとき
  
  $a* b\colon \mathbb{Z}/N\mathbb{Z} \to R;\ (a*b)[k] = \sum_{i, j \in \mathbb{Z}/N\mathbb{Z},\ i+j=k} a[i]\ b[j]$
- 巡回しないように気をつければ巡回畳み込みは普通の畳み込みとして使える。

($R$ は適当な環。競プロでは $\mathbb{Z}/998244353\mathbb{Z}$ が使われる)

注意点

mod 998244353 で NTT を使って畳み込みをする場合、（畳み込み後の）数列の長さの上限は 2$^{23} \fallingdotseq 8\times 10^{6}$
- $998244352 = 2^{23} \times 7 \times 17$ なので
畳み込みの結果、配列の長さが足りていないケースがある（配列外の値が欲しいことがある）。長さが足りない分（配列外）は0として扱えばよい。

問題例