Set Function (FZT, FMT, FWHT)
(src/math/set_function.hpp)

• View this file on GitHub
• Last update: 2023-04-23 19:32:20+09:00
• Include: #include "src/math/set_function.hpp"

概要

高速ゼータ変換 (Fast Zeta Transform) ，高速メビウス変換 (Fast Mobius Transform) や 高速ウォルシュ-アダマール変換 (Fast Walsh-Hadamard Transform) といった集合に関する諸変換及びそれに関連して bitwise な演算上の畳み込みを扱うライブラリ．

以下に記す時間計算量においては扱う列 $f$ 及び $g$ の長さを $2^n$ としている．

関数	効果	時間計算量
subset_zeta_transform(f)	$f(S) \leftarrow \sum_{T \subseteq S} f(T)$ と変換する．	$O(n2^n)$
subset_mobius_transform(f)	subset_zeta_transform の逆変換を行う．すなわち，$f(S) \leftarrow \sum_{T \subseteq S} (-1)^{|S| - |T|}g(T)$ と変換する．	$O(n2^n)$
superset_zeta_transform(f)	$f(S) \leftarrow \sum_{T \supseteq S} f(T)$ と変換する．	$O(n2^n)$
superset_mobius_transform(f)	superset_zeta_transform の逆変換を行う．すなわち，$f(S) \leftarrow \sum_{T \subseteq S} (-1)^{|S| - |T|}g(T)$ と変換する．	$O(n2^n)$
walsh_hadamard_transform(f, inv)	$f$ に対して Fast Walsh-Hadamard Transform を適用する．引数 inv を true にすると逆変換となる．	$O(n2^n)$
and_convolution(f, g)	列 $f, g$ を bitwise-and 演算に関して畳み込む．すなわち，$h_k = \sum_{i \& j = k} f_ig_j$ なる列 $h$ を返す．	$O(n2^n)$
or_convolution(f, g)	列 $f, g$ を bitwise-or 演算に関して畳み込む．すなわち，$h_k = \sum_{i \cup j = k} f_ig_j$ なる列 $h$ を返す．	$O(n2^n)$
xor_convolution(f, g)	列 $f, g$ を bitwise-xor 演算に関して畳み込む．すなわち，$h_k = \sum_{i \oplus j = k} f_ig_j$ なる列 $h$ を返す．	$O(n2^n)$

問題例

• Codeforces Round #259 (Div. 1) D. Little Pony and Elements of Harmony
  • 3 種の畳み込みは適切な変換によって列を各点積で合成できるようにし，最後にそれを逆変換するという仕組みになっている． よって，例えば同じ列を $n$ 回合成するというような操作も一度変換した後に列の各要素を $n$ 乗するといった操作によって容易に扱える．
• AtCoder Beginner Contest 212 H - Nim Counting
  • 上記に加えて，変換後の空間での線形性も扱っている．
• AtCoder Beginner Contest 215 H - Cabbage Master
• AtCoder Beginner Contest 220 H - Security Camera
• AtCoder Regular Contest 106 E - Medals

Links

• 高速ゼータ変換について - Qiita
• 高速ゼータ・メビウス変換 - Mister雑記
• 色々な畳み込み - kazuma8128’s blog

Verified with

• test/yosupo/bitwise_and_convolution.test.cpp
• test/yosupo/bitwise_xor_convolution.test.cpp
• test/yukicoder/1240.test.cpp
• test/yukicoder/1289.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

namespace set_function {

// subset sum : f(S) <- \sum_{T \subseteq S} f(T)
template <typename T> void subset_zeta_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] += f[j];
            }
        }
    }
}

// inverse of subset sum
// g = FZT(f) \iff f = FMT(g)
template <typename T> void subset_mobius_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] -= f[j];
            }
        }
    }
}

// superset sum : f(S) <- \sum_{T \supseteq S} f(T)
template <typename T> void superset_zeta_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] += f[j | i];
            }
        }
    }
}

// inverse of superset sum
// g = FZT(f) \iff f = FMT(g)
template <typename T> void superset_mobius_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] -= f[j | i];
            }
        }
    }
}

template <typename T> void walsh_hadamard_transform(std::vector<T>& f, bool inv = false) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                T x = f[j], y = f[j | i];
                f[j] = x + y, f[j | i] = x - y;
            }
        }
    }
    if (inv) {
        if (std::is_integral<T>::value) {
            for (auto& x : f) x /= n;
        } else {
            T inv_n = T(1) / f.size();
            for (auto& x : f) x *= inv_n;
        }
    }
}

template <typename T> std::vector<T> and_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    superset_zeta_transform(f);
    superset_zeta_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    superset_mobius_transform(f);
    return f;
}

template <typename T> std::vector<T> or_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    subset_zeta_transform(f);
    subset_zeta_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    subset_mobius_transform(f);
    return f;
}

template <typename T> std::vector<T> xor_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    walsh_hadamard_transform(f);
    walsh_hadamard_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    walsh_hadamard_transform(f, true);
    return f;
}

}  // namespace set_function

#line 2 "src/math/set_function.hpp"
#include <cassert>
#include <vector>

namespace set_function {

// subset sum : f(S) <- \sum_{T \subseteq S} f(T)
template <typename T> void subset_zeta_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] += f[j];
            }
        }
    }
}

// inverse of subset sum
// g = FZT(f) \iff f = FMT(g)
template <typename T> void subset_mobius_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] -= f[j];
            }
        }
    }
}

// superset sum : f(S) <- \sum_{T \supseteq S} f(T)
template <typename T> void superset_zeta_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] += f[j | i];
            }
        }
    }
}

// inverse of superset sum
// g = FZT(f) \iff f = FMT(g)
template <typename T> void superset_mobius_transform(std::vector<T>& f) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] -= f[j | i];
            }
        }
    }
}

template <typename T> void walsh_hadamard_transform(std::vector<T>& f, bool inv = false) {
    int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                T x = f[j], y = f[j | i];
                f[j] = x + y, f[j | i] = x - y;
            }
        }
    }
    if (inv) {
        if (std::is_integral<T>::value) {
            for (auto& x : f) x /= n;
        } else {
            T inv_n = T(1) / f.size();
            for (auto& x : f) x *= inv_n;
        }
    }
}

template <typename T> std::vector<T> and_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    superset_zeta_transform(f);
    superset_zeta_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    superset_mobius_transform(f);
    return f;
}

template <typename T> std::vector<T> or_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    subset_zeta_transform(f);
    subset_zeta_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    subset_mobius_transform(f);
    return f;
}

template <typename T> std::vector<T> xor_convolution(std::vector<T> f, std::vector<T> g) {
    assert(f.size() == g.size());
    walsh_hadamard_transform(f);
    walsh_hadamard_transform(g);
    for (int i = 0; i < int(f.size()); i++) f[i] *= g[i];
    walsh_hadamard_transform(f, true);
    return f;
}

}  // namespace set_function

Back to top page