読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

ゼータ変換$\zeta$とメビウス変換$\mu$はどちらも関数 $f:2^n \to R \quad(R: ring)$ に対する変換である。

その定義は次の通り。

$$ \zeta f(Y) = \sum_{X \subset Y} f(X) $$ $$ \mu f(Y) = \sum_{X \subset Y}(-1)^{|Y\setminus X|}f(X)$$

-1 が掛かっているのを無視すれば、両者の変換はほとんど同じである。 高速メビウス変換は高速ゼータ変換の逆変換になっている。つまり

$$ \mu \zeta f(Y) = f(Y) $$

が成り立つ。

この変換を高速に行うアルゴリズムを、高速ゼータ変換・高速メビウス変換と呼ぶ。C++ でのコードは次の通り。

vector<int> fast_zeta_transform(vector<int> f) {
    for (int i = 0; (1 << i) < f.size(); i++) {
        for (int j = 0; j < f.size(); j++) {
            if (j & 1 << i) {
                f[j] += f[j ^ 1 << i];
            }
        }
    }
    return f;
}

vector<int> fast_mobius_transform(vector<int> f) {
    for (int i = 0; (1 << i) < f.size(); i++) {
        for (int j = 0; j < f.size(); j++) {
            if (j & 1 << i) {
                f[j] -= f[j ^ 1 << i];
            }
        }
    }
    return f;
}

遷移を工夫した DP 程度のものである。動作が正しいことを示すには、下位 N ビットで正しく動作すると仮定して帰納法をすればいい。

ゼータ変換とメビウス変換はそれぞれ単体でも便利であるが、両方合わせると畳み込みを高速にできる。畳み込みは以下のように定義される。

$$ (f \ast g)(Y) = \sum_{S+T=Y} f(S)g(T) $$

ゼータ変換を適用すると単純になる。

$$ \zeta (f \ast g)(Y) = \zeta f (Y) \zeta g(Y) $$

証明は難しくない。

$$ \zeta (f \ast g)(Y) = \sum_{X \subset Y} \sum_{S+T=X} f(S)g(T) = \left( \sum_{X \subset Y} f(X) \right) \left( \sum_{X \subset Y} g(X) \right) $$