algorithm/superset_mobius_transform.cpp

View this file on GitHub
Last update: 2021-12-28 21:38:32+09:00

Depends on

utility/rep.cpp

Required by

algorithm/and_convolution.cpp

Verified with

test/and_convolution.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>
#include "../utility/rep.cpp"

template <class G> void superset_mobius_transform(std::vector<typename G::Type>& f) {
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = n; i >>= 1;)
        for (const int j : rep(n))
            if (j & i) f[j & ~i] = G::operation(f[j & ~i], G::inverse(f[j]));
}

#line 2 "algorithm/superset_mobius_transform.cpp"
#include <cassert>
#include <vector>
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 5 "algorithm/superset_mobius_transform.cpp"

template <class G> void superset_mobius_transform(std::vector<typename G::Type>& f) {
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    for (int i = n; i >>= 1;)
        for (const int j : rep(n))
            if (j & i) f[j & ~i] = G::operation(f[j & ~i], G::inverse(f[j]));
}