畳み込みの理論

• 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として扱えばよい。

畳み込みの典型例

• 和の確率分布は確率分布の畳み込み
• 和の頻度分布は頻度分布の畳み込み
• $\sum_{a=0}^A \sum_{b=0}^B f(a)\ g(b)\ h(a+b)$ は $O((A+B)\log(A+B))$ で計算できる

問題例

• AtCoder Typical Contest 001 C - 高速フーリエ変換
• JSC2019-final A - Equal Weight