高速ゼータ変換 高速メビウス変換

• ゼータ変換・メビウス変換を理解する - Qiita
• 高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog
  • 用語の定義に微妙なずれがあるが、それらを整理した記事
• 競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん

競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるのか不明だが、まぁそこは気にせず自分用メモとして書いておく。

集合についての数え上げを行う動的計画法の一種。

• ある $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)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。

i      0   1
A [   a0  a1 ]  元の配列
Z [ a0+a1 a1 ]  ゼータ変換後

$0 \subseteq 1$ なので、$Z[0]$ は $A[0]+A[1]$ となる。（たった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は逆演算できないので、メビウス変換は適用できないと思われる。

• 高速ゼータ変換の約数版 - noshi91のメモ