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

長さ $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) \, \mathrm{expected}$	$b$ が上に凸
※	$+$	$\times$	$\mathrm{O}(n (\log(n)) ^ 2)$	$\mathbb{C}$ , ※多変数畳み込み
※	$+$	$\times$	$\mathrm{O}(n (\log(n)) ^ 2 \log(\log(n)))$	環, ※多変数畳み込み