一生懸命書いたつもりですが、嘘が書いてあるかもしれませんし、カスみたいなことを書いているかもしれません。すみません(保身)
競プロにおける一般的な高速ゼータ変換
競プロにおいて、“ゼータ変換"や"メビウス変換"という用語は以下の意味で使われることが多いようです。
有限集合 \(X\)、(可換)半群 \(G\) を考える。
関数 \(f : 2^X \to G\), \(g : 2^X \to G\) が次の\((1)\)式または\((2)\)式を満たすとき、\(f\) から \(g\) を求めることをゼータ変換、\(g\) から \(f\) を求めることをメビウス変換と呼ぶ。
\begin{align} g(S) &= \sum_{T \subseteq S} f(T) \\ g(S) &= \sum_{T \supseteq S} f(T) \end{align}
このゼータ変換やメビウス変換を\(N\)次元累積和の手法を用いて高速化したのが、高速ゼータ変換や高速メビウス変換です。集合 \( X \) を \( |X| \) 次元の \( 2 \times 2 \times \dots \times 2 \) 格子とみなして、各次元ごとに累積和をとることでゼータ変換が成立するというのがこのアルゴリズムのキモなのです。(アルゴリズムの詳細には立ち入らないので、気になる方は記事末尾のリンクを参考にしてください)
本当は、ゼータ変換は集合の包含関係に限定されない一般的なかたちで定義されるものなのですが、そういった一般のゼータ変換に対して、高速化できるとは限りません。
畳み込み
ゼータ変換とある種の畳み込みには深い関係があります。(適切なゼータ変換を持ってきたとき、)関数 \( f \), \( g \) の畳み込みを \( h \) 、\( f \), \( g \), \( h \) のゼータ変換をそれぞれ \( \hat{f} \), \( \hat{g} \), \( \hat{h} \) とおくと、\( \hat{h} = \hat{f} * \hat{g} \) が成立するのです1(ただし、\(*\)は各点積)。よって、畳み込みの種類によっては、ゼータ変換 → 各点積 → メビウス変換 という手順によって畳み込みを高速化できることがあります。
上記 \( (1) \) のゼータ変換には $$ h(S) = \sum_{T \cup U = S} f(T) g(U) $$ が、\( (2) \) のゼータ変換には $$ h(S) = \sum_{T \cap U = S} f(T) g(U) $$ が対応しています。
高速ゼータ変換の自然な一般化について
ここまでで紹介した高速ゼータ変換は、始域が \( 2^X \) でした。これを始域が \( \mathbb{N}^X \) である関数に拡張することを考えてみましょう。
集合 \( X \) の部分集合 \( S \) は、写像 \( S : X \to \{0, 1\} \) と同一視できます(\( x \in S \iff S(x) = 1 \))。この同一視のもとで、\( 2^X \) 上の二項関係 \( \subseteq \) は、\( P \subseteq Q \iff \forall x \in X [ P(x) \leq Q(x) ] \) と定義できます。
集合 \( \mathbb{N}^X \) の元は \( X \) から \( \mathbb{N} \) への写像なので、この定義は \( 2^X \) から \( \mathbb{N}^X \) に自然に拡張でき、\( \mathbb{N}^X \) 上の二項関係 \( \subseteq \) を \( P \subseteq Q \iff \forall x \in X [ P(x) \leq Q(x) ] \) と定義することができます。
このとき、ゼータ変換も \( (1) \) や \( (2) \) を用いて定義することができます。そして、高速ゼータ変換も部分集合のときと同様に、\( X \) の元ごとに累積和をとることで実現できます。(ただし、\( \mathbb{N} \) について累積和をとると停止しないので適当なところで打ち切ってください)
また、\( (P \cup Q)(x) = \max(P(x), Q(x)),\ (P \cap Q)(x) = \min(P(x), Q(x)) \) と定義すれば、上で説明した畳み込みとの関係も成り立ちます。
例
正整数 \( n \) は、\( n(i) = (\text{素因数分解したときの、$i$番目の素数の指数}) \) とすることで \( \mathbb{N}^\mathbb{N} \) の元と自然な同一視ができます。
このとき、\( n \subseteq m \iff n \vert m,\ n \cup m = \mathrm{lcm}(n, m),\ n \cap m = \gcd(n, m) \) となるので2、GCD/LCM Convolution を高速ゼータ変換によって解くことができます(高速ゼータ変換を使わなくても十分高速なので、必要性はとても薄いですが)。
まとめ
え〜、実用性に乏しいという結論になってしまいましたが、まあ自然な一般化ができただけでもうれしいということでね(もし応用例を見つけたら教えてください)