noshi91のメモ

データ構造のある風景

私用メモ: 畳み込めるものまとめ

長さ  n 同士の列を畳み込むのが  \mathrm{O}(n ^ {2-\epsilon}) でできるやつ

 \displaystyle c _ k = \bigoplus _ {i \circ j = k} a _ i \otimes b _ j

 \circ  \oplus  \otimes 時間計算量 備考
 +  +  \times  \mathrm{O}(n \log (n))  \mathbb{C}, 高速フーリエ変換
 +  +  \times  \mathrm{O}(n \log(n) \log(\log(n))) 環, Schönhage–Strassen
 \cap  +  \times  \mathrm{O}(n \log (n)) 環, 高速ゼータ変換, メビウス変換
 \cup  +  \times  \mathrm{O}(n \log (n)) 環, 高速ゼータ変換, メビウス変換
 \Delta  +  \times  \mathrm{O}(n \log (n)) 環, 2 で割れる, 高速アダマール変換
 \amalg  +  \times  \mathrm{O}(n (\log (n)) ^ 2) 環, subset convolution
 \mathrm{gcd}  +  \times  \mathrm{O}(n \log (\log (n))) 環, 高速ゼータ変換, メビウス変換
 \mathrm{lcm}  +  \times  \mathrm{O}(n \log (\log (n))) 環, 高速ゼータ変換, メビウス変換
 \times \pmod{n}  +  \times  \mathrm{O}(n \log (n))  n素数,  \mathbb{C}, 高速フーリエ変換
 ※  +  \times  \mathrm{O}(n (\log (n) ) ^ 2)  \mathbb{C}, ※  i + j ただし  i \lt j, 高速フーリエ変換, 分割統治
 +  \max  \min  \mathrm{O}(n \sqrt{n \log (n)})
 +  \min  +  \mathrm{O}(n)  b が下に凸
 +  \min  +  \mathrm{O}(n \alpha(n))  b が上に凸
 +  \times  \mathrm{O}(n (\log(n)) ^ 2)  \mathbb{C}, ※多変数畳み込み
 +  \times  \mathrm{O}(n (\log(n)) ^ 2 \log(\log(n))) 環, ※多変数畳み込み

 \circ が集合の演算になっているものは、添え字を集合の整数表現と解釈して演算することを意味する。


実装など

n91lib_rs/subset_convolution.rs at master · noshi91/n91lib_rs · GitHub

n91lib_rs/max_min_convolution.rs at master · noshi91/n91lib_rs · GitHub

Concave Max Plus Convolution | Library

多変数畳み込み(切り捨て)のアルゴリズム – 37zigenのHP