Subset Möbius Transform
(algorithm/subset_mobius_transform.cpp)

• View this file on GitHub
• Last update: 2020-03-11 23:32:43+09:00

Depends on

• other/int_alias.cpp

Code

#include "other/int_alias.cpp"

#include <vector>

template <class G>
void subset_mobius_transform(std::vector<typename G::value_type> &a) {
  const usize n = a.size();
  usize i = 1;
  while (i < n)
    i *= 2;
  while (i != 1) {
    i /= 2;
    for (usize j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j] = G::operation(G::inverse(a[j & ~i]), a[j]);
    }
  }
}

/**
 * @brief Subset Möbius Transform
 */

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "algorithm/subset_mobius_transform.cpp"

#include <vector>

template <class G>
void subset_mobius_transform(std::vector<typename G::value_type> &a) {
  const usize n = a.size();
  usize i = 1;
  while (i < n)
    i *= 2;
  while (i != 1) {
    i /= 2;
    for (usize j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j] = G::operation(G::inverse(a[j & ~i]), a[j]);
    }
  }
}

/**
 * @brief Subset Möbius Transform
 */

Back to top page