メモ

yukicoderでゆるふわgolf

ゼータ変換とメビウス変換

高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablogで誤りを指摘されたので、反省の意味を込めて自分でちゃんと考えた。
メビウスの反転公式 - Wikipediaを元にしているけど、よくわかってないので間違ってたら教えて





追記
全部隣接代数 (順序理論) - Wikipediaに書いてました。ちゃんちゃん
追記終わり





○ゼータ変換・メビウス変換とは
Gを可換順序群、R可換環とする。
このとき、\{f:G^+\to R\}への作用素\zetaを、\displaystyle{(\zeta f)(x)=\sum_{0 \leq y\leq x}f(y)} により定める。
これをゼータ変換という。
もし\zeta\mu= \epsilonとなる\muが存在すれば、ゼータ変換には逆変換が存在し
\displaystyle{(\zeta^{-1} f)(x)=\sum_{0 \leq y\leq x}\mu(y)f(x-y)} となる。これをメビウス変換という。
ただし\
\epsilon(x)=\begin{cases}
    1 & (x=0) \\
    0 & (\text{otherwise})
  \end{cases}
である。


式の形を見れば分かる通り、これらは畳み込み積の計算であり、\zeta f=1*fである。
G=R=\mathbb{R}の場合などをイメージしてみよ)
\epsilonは畳み込みにおける単位元であり、1*\mu=\epsilonであるから、\muは定数関数1の畳み込みにおける逆元である。
このことから\mu*(\zeta f)=\mu*(1*f)=(\mu*1)*f=fにより、逆変換ができることが確かめられる。



は?



○競プロでよく見るやつ
・高速ゼータ変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
\displaystyle{g(S)=\sum_{T\subset S}f(T)}を高速に求める
・高速メビウス変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
\displaystyle{g(S)=\sum_{T\subset S}(-1)^{|T|}f(S\setminus T)}を高速に求める

「普通にやるとO(3^N)だけどO(N*2^N)でできるよ~」というやつ。
これは、べき集合P(X)を自然にG=\mathbb{Z}^Xへ持っていたと考えているようなもの(ほんとに?)
(もう少し仮定を弱めてGは群でなくてもよいのでは??)
※この例でいうとS\setminus Tのように、ある種の"差"が計算できる必要があると思っていたので、fの定義域を群にしたのだけど、wikipediaを見ると、区間を引数にとる関数だと思えばよかったらしい。なるほど



メビウスの反転公式
正整数上の関数f,gが
\displaystyle{g(n)=\sum_{d|n}f(d)}
を満たすとする。このとき
\displaystyle{f(n)=\sum_{d|n}\mu(d)g(n/d)}
が成り立つ。ただし\muメビウス関数

これはG=\mathbb{Q}^*/\{\pm 1\}\subset \mathbb{Z}^{\omega}に自然な順序x\leq y \iff y/x\in\mathbb{Z}を定めたものと言える



メビウス変換と包除原理
Uを集合とし、N個の集合A_i\subset Uがある。
X={1,...,N}とし、f:P(X)\to\mathbb{Z}
\displaystyle{f(S)=\left|\bigcap_{i\in S}A_i\right|} により定める。
\displaystyle{g(S)=\left|\bigcup_{i\in S}A_i\right|} とおくと、包除原理から
\displaystyle{
 \left|\bigcup_{i\in S}A_i\right|\\
=\sum_{\emptyset \neq T \subset S}(-1)^{|T|+1}\left|\bigcap_{i\in T}A_i\right|\\
=\sum_{\emptyset \neq T \subset S}(-1)^{|T|+1}f(T)\\
=\sum_{T \subset S}(-1)^{|T|+1}f(T)-f(\emptyset)\\
=(-1)^{|S|+1}\sum_{T \subset S}(-1)^{|S\setminus T|}f(T)-f(\emptyset)\\
=(-1)^{|S|+1}\sum_{T \subset S}(-1)^{|T|}f(S\setminus T)-f(\emptyset)\\
=(-1)^{|S|+1}(\zeta^{-1}f)(S)-f(\emptyset)\\
}
となる。
よってあらかじめf(\emptyset)を|U|ではなく|\emptyset|=0と定めておけば、g(S)=(-1)^{|S|+1}(\zeta^{-1}f)(S)となることが確かめられる。