ゼータ・メビウス変換とか包除原理とか畳み込みとか

数学的に厳密なことはしりません

高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog にあるようにゼータ・メビウス変換が色々あって何が何？？？と思っていたが，ゼータ変換・メビウス変換を理解する - Qiita によるとゼータ変換は半順序集合上で定義される演算らしく，半順序集合の実例としてべき集合を持ってくれば，ゼータ・メビウス変換(1)(2) がそれぞれ導かれるっぽい．

半順序集合：順序が定まってる集合だが，必ずしも2要素間に順序が定まっているわけではないようなやつ
例) $\mathbb{Z}^2$ で $(a,b) \leq (c,d) \iff a \leq c, b \leq d$
$(1,2) \leq (2,3) \leq (5,6)$ のように順序が定まるが， $(1,2)$ と $(2,1)$ を比較することはできない

ちゃんと書くと，集合 $X$ と集合 $X$ 上の二項関係 $\leq$ について反射律，推移律，反対称律が成り立っているならば $X$ は半順序集合と定義される

半順序集合上の関数 $f$ に対するゼータ変換が以下の通りに定義できる
$f_{\leq}(x) := \sum_{i \leq x} f(i) = f(i)\zeta(i,x)$
$f_{\geq}(x) := \sum_{i \geq x} f(i) = f(i)\zeta(x,i)$
ただし， $\zeta(a,b)=1 \quad (a \leq b)$
$\zeta(a,b)=0 \quad (\text{otherwise})$

メビウス変換はゼータ変換の逆変換で $\zeta(x,y)$ の逆行列で定まる

半順序集合: べき集合

たぶんこれが競プロで一番良く使われるやつで，半順序集合をべき集合にすると高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog に書かれている式が導かれる

集合 $U$ のべき集合， $S \subseteq T$ のときに $S \leq T$ と定める
これが半順序集合であることを確認する

反射律 $x \leq x$ → 明らかに成り立つ
推移律 $x \leq y, y \leq z \Rightarrow x \leq z$ → 明らかに成り立つ
反対称律 $x \leq y, y\leq x \Rightarrow x = y$ → お互いに部分集合なら一致する

$f_{\geq}(x)$ がゼータ・メビウス変換(1)に該当する．上位集合をまとめる．
ゼータ変換(1) → $S$ を部分集合として持つすべての集合 $T$ について $f(T)$ の総和
$g(S) := f_{\geq}(S) = \sum_{T \geq S} f(T) = \sum_{S \subseteq T} f(T)$

メビウス変換(1) → ゼータ変換(1)の逆変換
$f(S) = \sum_{S \subseteq T} (-1)^{|T \setminus S|} g(T)$

実装例
愚直に書くと部分集合の部分集合を列挙するのに $O(3^n)$ だが，うまくやると $O(n2^n)$ となる．多分この高速化した書き方のことを高速ゼータ・メビウス変換と呼ぶみたい？ fについて破壊的なのには注意

// ゼータ変換(1) f[i] = (iを部分集合としてもつjについてf[j]の総和)  
REP(i, n) REP(j, 1LL<<n) if(!(j&1LL<<i)) f[j] += f[j|(1LL<<i)];  
// メビウス変換(1)  
REP(i, n) REP(j, 1LL<<n) if(!(j&1LL<<i)) f[j] -= f[j|(1LL<<i)];

$f_{\leq}(x)$ がゼータ・メビウス変換(2)に該当する．下位集合をまとめる．
ゼータ変換(2) → $S$ の全ての部分集合 $T$ について $f(T)$ の総和
$g(S) := f_{\leq}(S) = \sum_{T \leq S} f(T) = \sum_{T \subseteq S} f(T)$

メビウス変換(2) → ゼータ変換(2)の逆変換
$f(S) = \sum_{T \subseteq S} (-1)^{S \setminus T} g(T)$

実装例
(1) と同じように $O(n2^n)$ で可能

// ゼータ変換(2)  
REP(i, n) REP(j, 1LL<<n) if(j&(1LL<<i)) f[j] += f[j^(1LL<<i)];  
// メビウス変換(2)  
REP(i, n) REP(j, 1LL<<n) if(j&(1LL<<i)) f[j] -= f[j^(1LL<<i)];

ここまで部分集合の和を求めるという形で書いたが必ずしも和である必要はなく，max等でも動く．（多分結合則とか逆元とかいる気がする．可換いる？抽象化わからん）

問題例
E - Or Plus Max

数列 $A_i$ が与えられるので $\max_{(i \text{ or } j) \leq K} A_i + A_j$ を各 $K$ に対して求める問題

2進数で1の位置の集合の包含関係を定めたときに $\text{max}(A_i+A_j) \quad ((i \text{ or } j) \subseteq K)$ が求められればよい． $(i \text{ or } j) \subseteq K$ は $i \subseteq K$ かつ $j \subseteq K$ と等しい．各 $i$ について $i \subseteq K$ となる全ての $K$ について，和の代わりに大きい方から上位2要素を求める．高速ゼータ変換の要領で $O(n2^n)$ でできる．

Submission #9667023 - AtCoder Regular Contest 100

包除原理

ゼータ変換の逆変換であるメビウス変換の式は包除原理の式そのまま
全ての集合に対して包除原理の答えを求めたいみたいなときは高速メビウス変換で $O(n2^n)$ でできる．
類題

畳み込み

フーリエ変換→積を計算→逆フーリエ変換で畳込みを計算できるのと同様に，ゼータ・メビウス変換でも似たようなことができる

ANDによる畳込み：ゼータ(2) (下位集合) → 積を計算 → メビウス(2) (下位集合)
ORによる畳込み：ゼータ(1) (上位集合) → 積を計算 → メビウス(1) (上位集合)
高速ゼータ変換, 高速メビウス変換, 添字ANDで畳み込み, 添字ORで畳み込み | るまライブラリ

半順序集合: 約数集合

二項関係を $y$ は $x$ の倍数にすると約数集合でのゼータ変換・メビウス変換的なやつと畳み込み - kazuma8128’s blog のように調和級数の要領で $O(N\log N)$ でゼータ・メビウス変換が求められる．さらに，高速ゼータ変換で $O(3^n)$ → $O(2^n)$ にしたのと同じように $O(N\log N)$ → $O(N\log\log N)$ にできるというのが高速ゼータ変換の約数版 - noshi91のメモに書いてある．

$g(x) = \sum_{x|y} f(y)$
$g(x) = \sum_{y|x} f(y)$
がゼータ変換でこの逆変換がメビウス変換

メビウス変換の式は約数系包除になってる

畳み込み

ANDやORによる畳込みが計算できたのと同様にGCD，LCMによる畳込みができる
GCDによる畳込み: $g(x) = \sum_{x|y} f(y)$
LCMによる畳込み: $g(x) = \sum_{y|x} f(y)$
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ

畳み込みが半群代数の積と思えることなど
【数学】畳み込み入門：Dirichlet積とゼータ変換・メビウス変換 | maspyのHP