高速ゼータ変換 高速メビウス変換
-
- 用語の定義に微妙なずれがあるが、それらを整理した記事
競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。
更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるか微妙だが、まぁそこは気にせず自分用メモとして書いておく。
定義
集合についての畳み込みを行う動的計画法の一種。
- ある $N$ 個のものがある
- それぞれを含むか含まないかの集合（部分集合）は全部で $2^N$ 通りある
A = {0, 1, 2}
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
- それぞれの部分集合 $S$ につき、何らかのスコア $f(S)$ が決まっている
- ある部分集合 $S_i$ について、$S_i \subseteq T$ となるような全ての $f(T)$ の総和を求めたい
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
f(S) 3 1 4 1 5 9 2 6
Si = {1}
→ T = {1}, {0, 1}, {1, 2}, {0, 1, 2}
f(T)の総和 4 + 5 + 2 + 6 = 17
- これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
f(S) 3 1 4 1 5 9 2 6
Z変換 31 21 17 18 11 15 8 6
- また、Z変換後から元の $f(S)$ を逆算する処理を「メビウス変換」という。
f(S) 3 1 4 1 5 9 2 6
ゼータ変換↓ ↑メビウス変換
Z変換 31 21 17 18 11 15 8 6
ただし、競プロ界隈ではよく使われるこの定義は限定的なものであり、本来のゼータ変換はもう少し広い範囲を指す。
定義揺れ
$S \subseteq T$ でなく $S \supseteq T$ であるような $T$ について求めることを指す場合もある。
ここでは、$S \subseteq T$ の方をゼータ変換①、$S \supseteq T$ の方をゼータ変換②と称する。
②は、部分集合の補集合を取ってから①のゼータ変換を行った結果と一緒になる。
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
スコア 3 1 4 1 5 9 2 6
Z変換② 3 4 7 4 13 14 10 31
補集合 {0, 1, 2}, {1, 2}, {0, 2}, {0, 1}, {2}, {1}, {0}, {}
スコア 3 1 4 1 5 9 2 6
Z変換① 3 4 7 4 13 14 10 31
実装方法
集合をbitで表す。
i 2 1 0
---------
0 0 0 0 ...{}
1 0 0 1 ...{0}
2 0 1 0 ...{1}
3 0 1 1 ...{0, 1}
4 1 0 0 ...{2}
5 1 0 1 ...{0, 2}
6 1 1 0 ...{1, 2}
7 1 1 1 ...{0, 1, 2}
元のスコアをこの順に対応させた配列を作り、以下の要領で更新する。
n = 3 # 集合の要素数
dp = [3, 1, 4, 5, 1, 9, 2, 6] # 2^n の長さ
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit == 0:
dp[i] += dp[i | bit]
print(dp)
# => [31, 21, 17, 11, 18, 15, 8, 6]
n = 3 # 集合の要素数
dp = [3, 1, 4, 5, 1, 9, 2, 6] # 2^n の長さ
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit:
dp[i] += dp[i ^ bit]
print(dp)
# => [3, 4, 7, 13, 4, 14, 10, 31]
n = 3 # 集合の要素数
dp = [31, 21, 17, 11, 18, 15, 8, 6] # ゼータ変換①後
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit == 0:
dp[i] -= dp[i | bit] # + を - にしただけ
print(dp)
# => [3, 1, 4, 5, 1, 9, 2, 6]
n = 3 # 集合の要素数
dp = [3, 4, 7, 13, 4, 14, 10, 31] # ゼータ変換②後
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit:
dp[i] -= dp[i ^ bit] # + を - にしただけ
print(dp)
# => [3, 1, 4, 5, 1, 9, 2, 6]
意味合い
ビット演算が、何やってるかよくわからない感を増しているが、意味合いは比較的単純であり、 集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。
$N=1$ の時
i 0 1 A [ a0 a1 ] 元の配列 Z [ a0+a1 a1 ] ゼータ変換後
$0 \subseteq 1$ なので、$Z[0]$ は $A[0]+A[1]$ となる。（たった2要素だが）後ろから累積和を取った感じ。
$N=2$ の時
bit列は1次元だが、2次元にして考えてみる。
A [ [ a00 a01 ]
[ a10 a11 ] ]
Z' [ [ a00+a01 a01 ] 横方向に後ろからの累積和（途中経過）
[ a10+a11 a11 ] ]
Z [ [ a00+a01+a10+a11 a01+a11 ] 縦方向に下からの累積和
[ a10+a11 a11 ] ]
次元が増えても、このように1次元ずつ後ろの要素を前の要素に足していくことを繰り返したものとなる。
バリエーション
加算以外の演算
ゼータ変換に適用する演算は必ずしも加算である必要は無い。 圏論でいう モノイド であれば、同様のアルゴリズムでまとめ上げることが可能である。
A [ [ a00 a01 ]
[ a10 a11 ] ]
↓演算を max としたゼータ変換
Z [ [ max(a00,a01,a10,a11) max(a01,a11) ]
[ max( a10, a11 ) max( a11 ) ] ]
それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。
包含以外の畳み込み
ゼータ変換後の $f$ を $\zeta(f)$ とする。ゼータ変換①を式で表すと
- $\zeta(f)(S) = \sum_{S \subseteq T} f(T)$
ここで $S$ はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。
- $\zeta(f)(i) = \sum_{i \ AND \ j=i} f(j)$
このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。
- ゼータ変換②
- $\zeta(f)(i) = \sum_{i \ OR \ j=i} f(j)$
- maxによる畳み込み
- $\zeta(f)(i) = \sum_{\max(i,j)=i} f(j)$
- 単なる累積和っぽい?
- 最大公約数、最小公倍数による畳み込み
- $\zeta(f)(i) = \sum_{\gcd(i,j)=i} f(j)$
- $i$ の倍数であるような $j$
- $\zeta(f)(i) = \sum_{{\rm lcm}(i,j)=i} f(j)$
- $i$ の約数であるような $j$
