Fast Möbius transform (Subsets)
(Mylib/Convolution/fast_mobius_transform_subset.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• fast_mobius_transform_subset(f[N], op = std::minus())
  • Nは2の累乗
  • $g(S) = \sum_{T \subseteq S} f(T) * (-1) ^ {\vert S \vert - \vert T \vert}$

Requirements

Notes

Problems

• AOJ 2446 Enumeration

References

Required by

• Convolution (Index bitwise OR) (Mylib/Convolution/convolution_or.cpp)
• Subset convolution (Mylib/Convolution/subset_convolution.cpp)

Verified with

• test/aoj/2446/main.test.cpp
• test/yosupo-judge/bitwise_and_convolution/main.or.test.cpp
• test/yosupo-judge/subset_convolution/main.test.cpp

Code

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

namespace haar_lib {
  template <typename T, typename Func = std::minus<T>>
  std::vector<T> fast_mobius_transform_subset(std::vector<T> f, const Func &op = std::minus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (j & i) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib

#line 2 "Mylib/Convolution/fast_mobius_transform_subset.cpp"
#include <cassert>
#include <functional>
#include <vector>

namespace haar_lib {
  template <typename T, typename Func = std::minus<T>>
  std::vector<T> fast_mobius_transform_subset(std::vector<T> f, const Func &op = std::minus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (j & i) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib

Back to top page