文書の過去の版を表示しています。
高速ゼータ変換 高速メビウス変換
-
- 用語の定義に微妙なずれがあるが、それらを整理した記事
競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるのか不明だが、まぁそこは気にせず自分用メモとして書いておく。
定義
集合についての数え上げを行う動的計画法の一種。
- ある $N$ 個のものがある
- それぞれを含むか含まないかの集合(部分集合)は全部で $2^N$ 通りある
A = {0, 1, 2} 部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
- それぞれの部分集合につき、何らかのスコアが決まっている
- ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求める
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2} スコア 3 1 4 1 5 9 2 6 S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} 4 + 5 + 2 + 6 = 17
- これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2} スコア 3 1 4 1 5 9 2 6 Z変換 31 21 17 18 11 15 8 6
- また、Z変換後から元のスコアを逆算する処理を「メビウス変換」という。
スコア 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次元ずつ後ろの要素を前の要素に足していくことを繰り返したものとなる。