目次
まえがき
この記事はこのサイトの書き心地のテスト用に書かれたものです。行間とかおかしいかもしれないよ
この記事に登場する数列の長さは全て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$となる
添字のorに関する畳み込み
数列$a,b$が与えられる。数列$c_i = \sum_{i=j \cup k}a_jb_k$を出来るだけ高速に求めてください。
これは上と同様の方法で求められる:
- 高速ゼータ変換をするときに、包含関係をさっきと逆にする:$A_i = \sum_{j \sub i}a_j$
- 高速メビウス変換を行うときも、さっきと包含関係が逆のとき用のやつを使う。
証明もさっきと同様にできる
おわりに
応用例とか、他の畳み込みの高速化の話とか、これの背景にある数学(半群代数)とかの話とか出来たらいいよね
コメントを投稿する
コメントを投稿してみたコメントを編集した