競技プログラミングにおいて、ゼータ・メビウス変換はよく用いられる手法です。 この言葉はいくつかの文脈(用途)で使われるので、それを分類します。 以下では、\(f\)を多次元配列として、\(f\)をゼータ変換したものを\(g\)と表します。

①累積和と差分

ゼータ変換は多次元累積和、メビウス変換は多次元差分をとることに相当します。 たとえば\(f\)という\(N\)次元配列np.arrayは

for i in range(N):
  np.cumsum(f,axis=i,out=f)

とすることでゼータ変換できます。 \(f\)全体から\(g\)全体を計算するというものです。

②包除原理

\(f\)のある要素は、\(g\)のいくつかの要素を求めてそれらを足したり引いたりすることで求めることができます。 たとえば\(f\)が\(2\)次元配列とすると、\(f[2][5]=g[2][5]-g[1][5]-g[2][4]+g[1][4]\)となります。

\(g[i]=\sum_{j|i}f[i]\)

という変換はゼータ変換に相当しており、この場合の包除原理にはメビウスの反転公式という名前がついています。

③\(max\)(または\(min\))に相当する畳み込みの高速化

長さ\(N\)の\(2\)つの配列\(A,B\)に対して、

\(C[k]=\sum_{\max(i,j)=k}A[i]B[j]\)

となる\(C\)を計算したいとします。 愚直に計算すると\(O(N^2)\)ですが、\(A,B,C\)をそれぞれ\(A',B',C'\)とすると

\(A'[i]*B'[i]=C'[i] (i=1,2,...,N)\)

が成り立つので、\(A,B\)をゼータ変換した\(A',B'\)から\(C'\)を求め、さらにそれをメビウス変換することで\(C\)を\(O(N)\)で求めることができます。 \(lcm\)や\(or\)は\(max\)に相当するので、

\(C[k]=\sum_{\mathrm{lcm}(i,j)=k}A[i]B[j]\)

\(C[k]=\sum_{i\,\mathrm{or}\,j=k}A[i]B[j]\)

も高速に求めることができます。 同様に、\(min\)に相当する演算についての畳み込みも高速に計算できます。