Bitwise XOR convolution (tools/xor_convolution.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-25 23:49:58+09:00
• Include: #include "tools/xor_convolution.hpp"

template <std::ranges::input_range R1, std::ranges::input_range R2>
std::vector<std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>> xor_convolution(R1&& a, R2&& b);

Given two sequences $(a_0, a_1, \ldots, a_{N - 1})$ and $(b_0, b_1, \ldots, b_{N - 1})$, it returns the sequence $(c_0, c_1, \ldots, c_{N - 1})$ where

\[\begin{align*} c_k &= \sum_{i \oplus j = k} a_i b_j \end{align*}\]

Constraints

• $|a| = |b|$
• $N$ is a power of two.
• If std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>> is tools::modint_compatible, then its modulus is odd.

Time Complexity

• $O(N \log N)$

License

• CC0

Author

• anqooqie

Depends on

• 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 a type compatible with atcoder::static_modint (tools/modint_compatible.hpp)
• tools::integral except for bool (tools/non_bool_integral.hpp)

Verified with

• tests/xor_convolution.test.cpp

Code

#ifndef TOOLS_XOR_CONVOLUTION_HPP
#define TOOLS_XOR_CONVOLUTION_HPP

#include <cassert>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#include "tools/has_single_bit.hpp"
#include "tools/modint_compatible.hpp"

namespace tools {
  namespace detail::xor_convolution {
    template <typename T>
    void fwht(std::vector<T>& a) {
      const int N = a.size();
      assert(tools::has_single_bit(N));

      for (int w = 1; w < N; w <<= 1) {
        for (int i = 0; i < N; ++i) {
          if ((i & w) == 0) {
            T x = a[i];
            T y = a[i | w];
            a[i] = x + y;
            a[i | w] = x - y;
          }
        }
      }
    }
  }

  template <std::ranges::input_range R1, std::ranges::input_range R2>
  std::vector<std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>> xor_convolution(R1&& a_orig, R2&& b_orig) {
    using T = std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>;
    auto a = std::forward<R1>(a_orig) | std::ranges::to<std::vector<T>>();
    auto b = std::forward<R2>(b_orig) | std::ranges::to<std::vector<T>>();
    const int N = a.size();
    assert(std::ssize(b) == N);
    assert(tools::has_single_bit(N));

    tools::detail::xor_convolution::fwht(a);
    tools::detail::xor_convolution::fwht(b);

    std::vector<T> c(N);
    for (int i = 0; i < N; ++i) {
      c[i] = a[i] * b[i];
    }
    tools::detail::xor_convolution::fwht(c);

    if constexpr (tools::modint_compatible<T>) {
      assert(T::mod() % 2 == 1);
      const auto inv_N = T(N).inv();
      for (int i = 0; i < N; ++i) {
        c[i] *= inv_N;
      }
    } else {
      for (int i = 0; i < N; ++i) {
        c[i] /= T(N);
      }
    }
    return c;
  }
}

#endif

#line 1 "tools/xor_convolution.hpp"



#include <cassert>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#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"



#include <concepts>
#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 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/modint_compatible.hpp"



#line 6 "tools/modint_compatible.hpp"

namespace tools {
  template <typename T>
  concept modint_compatible = std::regular<std::remove_cv_t<T>>
    && std::equality_comparable<std::remove_cv_t<T>>
    && std::constructible_from<std::remove_cv_t<T>, bool>
    && std::constructible_from<std::remove_cv_t<T>, char>
    && std::constructible_from<std::remove_cv_t<T>, int>
    && std::constructible_from<std::remove_cv_t<T>, long long>
    && std::constructible_from<std::remove_cv_t<T>, unsigned int>
    && std::constructible_from<std::remove_cv_t<T>, unsigned long long>
    && requires(std::remove_cv_t<T> a, std::remove_cv_t<T> b, int v_int, long long v_ll) {
      { std::remove_cv_t<T>::mod() } -> std::convertible_to<int>;
      { std::remove_cv_t<T>::raw(v_int) } -> std::same_as<std::remove_cv_t<T>>;
      { a.val() } -> std::convertible_to<int>;
      { ++a } -> std::same_as<std::remove_cv_t<T>&>;
      { --a } -> std::same_as<std::remove_cv_t<T>&>;
      { a++ } -> std::same_as<std::remove_cv_t<T>>;
      { a-- } -> std::same_as<std::remove_cv_t<T>>;
      { a += b } -> std::same_as<std::remove_cv_t<T>&>;
      { a -= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a *= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a /= b } -> std::same_as<std::remove_cv_t<T>&>;
      { +a } -> std::same_as<std::remove_cv_t<T>>;
      { -a } -> std::same_as<std::remove_cv_t<T>>;
      { a.pow(v_ll) } -> std::same_as<std::remove_cv_t<T>>;
      { a.inv() } -> std::same_as<std::remove_cv_t<T>>;
      { a + b } -> std::same_as<std::remove_cv_t<T>>;
      { a - b } -> std::same_as<std::remove_cv_t<T>>;
      { a * b } -> std::same_as<std::remove_cv_t<T>>;
      { a / b } -> std::same_as<std::remove_cv_t<T>>;
    };
}


#line 12 "tools/xor_convolution.hpp"

namespace tools {
  namespace detail::xor_convolution {
    template <typename T>
    void fwht(std::vector<T>& a) {
      const int N = a.size();
      assert(tools::has_single_bit(N));

      for (int w = 1; w < N; w <<= 1) {
        for (int i = 0; i < N; ++i) {
          if ((i & w) == 0) {
            T x = a[i];
            T y = a[i | w];
            a[i] = x + y;
            a[i | w] = x - y;
          }
        }
      }
    }
  }

  template <std::ranges::input_range R1, std::ranges::input_range R2>
  std::vector<std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>> xor_convolution(R1&& a_orig, R2&& b_orig) {
    using T = std::common_type_t<std::ranges::range_value_t<R1>, std::ranges::range_value_t<R2>>;
    auto a = std::forward<R1>(a_orig) | std::ranges::to<std::vector<T>>();
    auto b = std::forward<R2>(b_orig) | std::ranges::to<std::vector<T>>();
    const int N = a.size();
    assert(std::ssize(b) == N);
    assert(tools::has_single_bit(N));

    tools::detail::xor_convolution::fwht(a);
    tools::detail::xor_convolution::fwht(b);

    std::vector<T> c(N);
    for (int i = 0; i < N; ++i) {
      c[i] = a[i] * b[i];
    }
    tools::detail::xor_convolution::fwht(c);

    if constexpr (tools::modint_compatible<T>) {
      assert(T::mod() % 2 == 1);
      const auto inv_N = T(N).inv();
      for (int i = 0; i < N; ++i) {
        c[i] *= inv_N;
      }
    } else {
      for (int i = 0; i < N; ++i) {
        c[i] /= T(N);
      }
    }
    return c;
  }
}

Back to top page