ゼータ変換・メビウス変換
概要
ゼータ変換は「2次元累積和を$ d次元に拡張して、添字を整数にまとめたもの」というイメージ
累積和→2次元累積和「縦に累積和してから横に累積和」→3次元累積和「縦にやって横にやって高さにやる」→……
計算量は添字の上限を$ Nとして、$ O(dN)
一般の場合
愚直に実装するとこんな感じか
code:zeta.py
# 擬似コード
for i in range(d): # 累積和取る次元
lowB = product(B:i) # i次元未満の部分 for lower in range(lowB):
for upper in range(upB, N, upB):
offset = lower + upper
j *= lowB
ループがややこしいが、lowB * N // upB * B[i] == Nから計算量が$ O(dN)になってることがわかる。
加算の部分はモノイドならOK。
結合則$ (a \cdot b) \cdot c = a \cdot (b \cdot c)と単位元$ a \cdot e = e \cdot a = aなやつ
メビウス変換もする場合は、逆演算も必要そう。
$ \maxとかはモノイドだが逆演算ができないのでだめぽ
bit演算
競プロ的に、あるいは集合的にはB = [2, 2, ...]となるbitなゼータ変換を考えることが多い。
bit演算でスッキリ書けて、
code:zeta_bit.py
for i in range(d):
i = 1 << i # i番目のbitについて累積和
for j in range(N):
if j & i: # i番目のbitが立ってるjについて
Aj += Aj^i # i番目のbitを下ろしたものを足す 約数
添字$ nを素因数分解した結果$ n = 2^{e_1}3^{e_2}5^{e_3}\dotsの指数部分$ (e_1, e_2, e_3,\dots)を添字とする配列とみなしてゼータ変換できる。
code:zeta_div.py
primes = getPrimes(N) # 素数の一覧を入手しておく
for p in primes:
for i in range(1, N//p):
畳み込み
2つの数列$ A,Bについて、$ \maxによる畳み込み
$ C[x] = \sum_{0 \le i,j \lt N, \max(i, j) = x} A[i]B[j]
を求めることができる。（$ \max はbit演算では$ \text{OR} 、約数では$ \text{lcm} になる。）
$ A,B,Cのゼータ変換を$ \zeta A,\zeta B,\zeta Cとすると、
$ (\zeta C)[x] = (\zeta A)[x] (\zeta B)[x]
が成り立つ（らしい）ので、
$ A, Bをゼータ変換する
各点の積を$ Cとする
$ Cをメビウス変換する
で求まる。
一般化
これが使える条件は
添字に半順序を定義できる
シンプル$ d次元配列では$ x \le y \iff全ての次元で$ x_i \le y_i
集合では$ x \le y \iff x \subset y
約数では$ x \le y \iff yは$ xで割り切れる
「結び」「交わり」が存在する
結び$ \iff a,bより大きいものの中の最小$ \iff: a \lor b
交わり$ \iff a,bより小さいものの中の最大$ \iff: a \land b
シンプル$ d次元配列では各次元で$ \max (a_i, b_i)や$ \min (a_i, b_i)
集合では$ a \cup bや$ a \cap b
約数では$ \text{lcm} (a,b)や$ \text{gcd} (a,b)
問題例
参考