Subset Transform (Zeta / Möbius)
(set_function/subset_transform.hpp)

• View this file on GitHub
• Last update: 2023-10-26 18:43:58+09:00
• Include: #include "set_function/subset_transform.hpp"

説明

$N$ 要素の集合の冪集合に値が定義されている配列 $a$ について $\zeta a$ を部分集合の累積和とする。 つまり以下の式を満たす $\zeta a$ を求めることを $\zeta$ 変換という。逆変換をメビウス変換という。

\[\zeta a_{S} = \sum_{T \subset S} a_T\]

いずれも、 $O(N2^N)$ で変換することができる。

Required by

• Bitwise OR Convolution (convolution/or_convolution.hpp)
• Chromatic Number (彩色数) (graph/chromatic_number.hpp)

Verified with

• test/convolution/Bitwise_OR_Convolution.test.cpp
• test/graph/Chromatic_Number.test.cpp

Code

#pragma once

#include <bit>
#include <cassert>
#include <vector>

namespace ebi {

template <class T> std::vector<T> subset_zeta(const std::vector<T> &a) {
    int n = std::bit_width(a.size()) - 1;
    assert((1 << n) == (int)a.size());
    std::vector<T> ra = a;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                ra[t] += ra[s];
            }
        }
    }
    return ra;
}

template <class T> std::vector<T> subset_mobius(const std::vector<T> &ra) {
    int n = std::bit_width(ra.size()) - 1;
    assert((1 << n) == (int)ra.size());
    std::vector<T> a = ra;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                a[t] -= a[s];
            }
        }
    }
    return a;
}

}  // namespace ebi

#line 2 "set_function/subset_transform.hpp"

#include <bit>
#include <cassert>
#include <vector>

namespace ebi {

template <class T> std::vector<T> subset_zeta(const std::vector<T> &a) {
    int n = std::bit_width(a.size()) - 1;
    assert((1 << n) == (int)a.size());
    std::vector<T> ra = a;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                ra[t] += ra[s];
            }
        }
    }
    return ra;
}

template <class T> std::vector<T> subset_mobius(const std::vector<T> &ra) {
    int n = std::bit_width(ra.size()) - 1;
    assert((1 << n) == (int)ra.size());
    std::vector<T> a = ra;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                a[t] -= a[s];
            }
        }
    }
    return a;
}

}  // namespace ebi

Back to top page