Subset Möbius transform (tools/subset_moebius.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-07 00:03:37+09:00
• Include: #include "tools/subset_moebius.hpp"

(1)
template <typename InputIterator, typename OutputIterator>
void subset_moebius(InputIterator begin, InputIterator end, OutputIterator result);

(2)
template <typename RandomAccessIterator>
void subset_moebius(RandomAccessIterator begin, RandomAccessIterator end);

• (1)
  • Given a sequence $(b_0, b_1, \ldots, b_{N - 1})$ from begin and end, it stores the sequence $(a_0, a_1, \ldots, a_{N - 1})$ that satisfies the following relational equation to result.
• (2)
  • Given a sequence $(b_0, b_1, \ldots, b_{N - 1})$ from begin and end, it stores the sequence $(a_0, a_1, \ldots, a_{N - 1})$ that satisfies the following relational equation to begin.

The following relationship holds between $a$ and $b$.

\[\begin{align*} b_i &= \sum_{\substack{0 \leq j < N \\ (i~\mathrm{OR}~j) = i}} a_j \end{align*}\]

Constraints

• None
  • Note that result in (1) can be the same as begin, but it would be better to use (2) in that case.

Time Complexity

• $O(N \log N)$

License

• CC0

Author

• anqooqie

Depends on

• $2^x$ (tools/pow2.hpp)

Required by

• Bitwise OR convolution (tools/or_convolution.hpp)

Verified with

• tests/or_convolution/different_lengths.test.cpp
• tests/or_convolution/regular.test.cpp
• tests/subset_moebius.test.cpp

Code

#ifndef TOOLS_SUBSET_MOEBIUS_HPP
#define TOOLS_SUBSET_MOEBIUS_HPP

#include <iterator>
#include <vector>
#include <algorithm>
#include "tools/pow2.hpp"

namespace tools {
  template <typename RandomAccessIterator>
  void subset_moebius(const RandomAccessIterator begin, const RandomAccessIterator end) {
    const int N = end - begin;

    for (int w = 0; ::tools::pow2(w) < N; ++w) {
      for (int i = 0; ; i += ::tools::pow2(w)) {
        for (; !((i >> w) & 1); ++i) {
          if (!(i + ::tools::pow2(w) < N)) goto NEXT_W;
          begin[i + ::tools::pow2(w)] -= begin[i];
        }
      }
    NEXT_W:
      ;
    }
  }

  template <typename InputIterator, typename OutputIterator>
  void subset_moebius(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> b(begin, end);
    ::tools::subset_moebius(b.begin(), b.end());
    ::std::move(b.begin(), b.end(), result);
  }
}

#endif

#line 1 "tools/subset_moebius.hpp"



#include <iterator>
#include <vector>
#include <algorithm>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#include <cstddef>

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 8 "tools/subset_moebius.hpp"

namespace tools {
  template <typename RandomAccessIterator>
  void subset_moebius(const RandomAccessIterator begin, const RandomAccessIterator end) {
    const int N = end - begin;

    for (int w = 0; ::tools::pow2(w) < N; ++w) {
      for (int i = 0; ; i += ::tools::pow2(w)) {
        for (; !((i >> w) & 1); ++i) {
          if (!(i + ::tools::pow2(w) < N)) goto NEXT_W;
          begin[i + ::tools::pow2(w)] -= begin[i];
        }
      }
    NEXT_W:
      ;
    }
  }

  template <typename InputIterator, typename OutputIterator>
  void subset_moebius(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> b(begin, end);
    ::tools::subset_moebius(b.begin(), b.end());
    ::std::move(b.begin(), b.end(), result);
  }
}

Back to top page