In-place superset Möbius transform (tools/superset_moebius_inplace.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-02-21 18:33:47+09:00
• Include: #include "tools/superset_moebius_inplace.hpp"

template <std::ranges::random_access_range R>
requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
void superset_moebius_inplace(R&& b);

template <tools::commutative_group G, std::ranges::random_access_range R>
requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
void superset_moebius_inplace(R&& b);

Assume that the following relationship holds between $a = (a_0, a_1, \ldots, a_{N - 1})$ and $b = (b_0, b_1, \ldots, b_{N - 1})$.

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

Given $b$, it updates $b$ to $a$.

Constraints

• $N$ is a power of two.

Time Complexity

• $O(N \log N)$

License

• CC0

Author

• anqooqie

Depends on

• Concept for arithmetic types including tools::int128_t and tools::uint128_t (tools/arithmetic.hpp)
• Concept for commutative group (tools/commutative_group.hpp)
• Concept for commutative monoid (tools/commutative_monoid.hpp)
• Concept for group (tools/group.hpp)
• Typical groups (tools/groups.hpp)
• Check whether a given integer is $2^n$ (tools/has_single_bit.hpp)
• Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• Concept for monoid (tools/monoid.hpp)
• tools::integral except for bool (tools/non_bool_integral.hpp)
• $2^x$ (tools/pow2.hpp)

Required by

• Bitwise AND convolution (tools/and_convolution.hpp)
• Superset Möbius transform (tools/superset_moebius.hpp)

Verified with

• tests/and_convolution.test.cpp
• tests/superset_moebius.test.cpp

Code

#ifndef TOOLS_SUPERSET_MOEBIUS_INPLACE_HPP
#define TOOLS_SUPERSET_MOEBIUS_INPLACE_HPP

#include <cassert>
#include <iterator>
#include <ranges>
#include <utility>
#include "tools/commutative_group.hpp"
#include "tools/groups.hpp"
#include "tools/has_single_bit.hpp"
#include "tools/pow2.hpp"

namespace tools {
  template <tools::commutative_group G, std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void superset_moebius_inplace(R&& b) {
    const int N = std::ranges::distance(b);
    assert(tools::has_single_bit(N));

    for (int w = 0; tools::pow2(w) < N; ++w) {
      for (int i = 0; i < N; i += tools::pow2(w)) {
        for (; !((i >> w) & 1); ++i) {
          std::ranges::begin(b)[i] = G::op(std::ranges::begin(b)[i], G::inv(std::ranges::begin(b)[i + tools::pow2(w)]));
        }
      }
    }
  }

  template <std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void superset_moebius_inplace(R&& b) {
    tools::superset_moebius_inplace<tools::groups::plus<std::ranges::range_value_t<R>>>(std::forward<R>(b));
  }
}

#endif

#line 1 "tools/superset_moebius_inplace.hpp"



#include <cassert>
#include <iterator>
#include <ranges>
#include <utility>
#line 1 "tools/commutative_group.hpp"



#line 1 "tools/commutative_monoid.hpp"



#line 1 "tools/monoid.hpp"



#include <concepts>

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 5 "tools/commutative_monoid.hpp"

namespace tools {
  template <typename M>
  concept commutative_monoid = tools::monoid<M>;
}


#line 1 "tools/group.hpp"



#line 6 "tools/group.hpp"

namespace tools {
  template <typename G>
  concept group = tools::monoid<G> && requires(typename G::T x) {
    { G::inv(x) } -> std::same_as<typename G::T>;
  };
}


#line 6 "tools/commutative_group.hpp"

namespace tools {
  template <typename G>
  concept commutative_group = tools::group<G> && tools::commutative_monoid<G>;
}


#line 1 "tools/groups.hpp"



#include <cstddef>
#include <type_traits>
#line 1 "tools/arithmetic.hpp"



#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 6 "tools/arithmetic.hpp"

namespace tools {
  template <typename T>
  concept arithmetic = tools::integral<T> || std::floating_point<T>;
}


#line 7 "tools/groups.hpp"

namespace tools {
  namespace groups {
    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& x, const T& y) {
        return x ^ y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return x;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& x) {
        return e() / x;
      }
    };

    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& x, const T& y) {
        return x + y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return -x;
      }
    };
  }
}


#line 1 "tools/has_single_bit.hpp"



#include <bit>
#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = tools::is_signed<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = tools::is_unsigned<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename tools::make_unsigned<T>::type;
}


#line 1 "tools/non_bool_integral.hpp"



#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 12 "tools/has_single_bit.hpp"

namespace tools {
  namespace detail::has_single_bit {
    template <tools::non_bool_integral T>
    struct impl {
      constexpr bool operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
        assert(x >= 0);
        return impl<tools::make_unsigned_t<T>>{}(x);
      }
      constexpr bool operator()(const T x) const noexcept(noexcept(std::has_single_bit(x))) requires tools::is_unsigned_v<T> {
        return std::has_single_bit(x);
      }
    };
  }

  template <typename T>
  constexpr decltype(auto) has_single_bit(T&& x) noexcept(noexcept(tools::detail::has_single_bit::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
    return tools::detail::has_single_bit::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
  }
}


#line 1 "tools/pow2.hpp"



#line 5 "tools/pow2.hpp"
#include <limits>
#line 7 "tools/pow2.hpp"

namespace tools {
  template <tools::integral T>
  constexpr T pow2(const T x) noexcept {
    assert(0 <= x && x < std::numeric_limits<T>::digits);
    return T(1) << x;
  }
}


#line 12 "tools/superset_moebius_inplace.hpp"

namespace tools {
  template <tools::commutative_group G, std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void superset_moebius_inplace(R&& b) {
    const int N = std::ranges::distance(b);
    assert(tools::has_single_bit(N));

    for (int w = 0; tools::pow2(w) < N; ++w) {
      for (int i = 0; i < N; i += tools::pow2(w)) {
        for (; !((i >> w) & 1); ++i) {
          std::ranges::begin(b)[i] = G::op(std::ranges::begin(b)[i], G::inv(std::ranges::begin(b)[i + tools::pow2(w)]));
        }
      }
    }
  }

  template <std::ranges::random_access_range R>
  requires std::ranges::output_range<R, std::ranges::range_value_t<R>>
  void superset_moebius_inplace(R&& b) {
    tools::superset_moebius_inplace<tools::groups::plus<std::ranges::range_value_t<R>>>(std::forward<R>(b));
  }
}

Back to top page