まえがき

この記事はこのサイトの書き心地のテスト用に書かれたものです。行間とかおかしいかもしれないよ
この記事に登場する数列の長さは全てnとする

前提知識

整数間の$\cap,\cup,\sub,\supset$：整数を2進数にして、i 桁目が1なら i 番目の要素がある、0なら無いとみなしたとき、整数を集合とみなすことができ、包含関係などを定義できる。例えば、$1101_{(2)} \supset 100_{(2)}, 1001_{(2)} \cup 11_{(2)} = 1011_{(2)}$
高速ゼータ変換：数列$a$が与えられた時に$A_i = \sum_{i \sub j}a_j, B_i = \sum_{i \supset j}a_j$を$O(n\log{n})$で求められるすげーやつ
高速メビウス変換：高速ゼータ変換の逆変換。これも$O(n\log{n})$で計算できる。

添字のandに関する畳み込み

数列$a,b$が与えられる。数列$c_i = \sum_{i=j \cap k}a_jb_k$を出来るだけ高速に求めてください。

これは以下の方法で求められる：

まず$a,b$を高速ゼータ変換し、それを$A,B$とする
$C_i=A_iB_i$とする
$C$を高速メビウス変換（高速ゼータ変換の逆変換）したものが実は求めたい$c$となっている！（すごい）

合計計算量は$O(n\log{n})$（愚直にやったら$O(n^2)$）

証明

$C_i = A_iB_i = \left(\sum_{i \sub j}a_j\right)\left(\sum_{i \sub j}b_j\right) = \sum_{i \sub j,k}a_jb_k$
ところで、$i\sub j,k$と$i\sub j \cap k$は同値なので、
$\sum_{i \sub j,k}a_jb_k = \sum_{i \sub j\cap k}a_jb_k$
これを高速メビウス変換することで、確かに$\sum_{i = j \cap k}a_jb_k$となる