set/hadamard-transform.hpp

View this file on GitHub
Last update: 2025-10-10 17:35:46+09:00
Include: #include "set/hadamard-transform.hpp"

Required by

set/xor-convolution.hpp

Verified with

verify/set/LC_bitwise_xor_convolution.test.cpp

Code

#pragma once

template <class T>
void HadamardTransform(vector<T>& f, bool inv = false) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        T x = f[j], y = f[j | i];
        f[j] = x + y, f[j | i] = x - y;
      }
    }
  }
  if (inv) {
    if constexpr (is_integral<T>::value) {
      for (auto& x : f) x /= n;
    } else {
      T invn = T(1) / T(f.size());
      for (auto& x : f) x *= invn;
    }
  }
}

#line 2 "set/hadamard-transform.hpp"

template <class T>
void HadamardTransform(vector<T>& f, bool inv = false) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        T x = f[j], y = f[j | i];
        f[j] = x + y, f[j | i] = x - y;
      }
    }
  }
  if (inv) {
    if constexpr (is_integral<T>::value) {
      for (auto& x : f) x /= n;
    } else {
      T invn = T(1) / T(f.size());
      for (auto& x : f) x *= invn;
    }
  }
}