set/xor-convolution.hpp

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

Depends on

set/hadamard-transform.hpp

Verified with

verify/set/LC_bitwise_xor_convolution.test.cpp

Code

#pragma once

#include "./hadamard-transform.hpp"

template <class T>
vector<T> XorConvolution(vector<T> a, vector<T> b) {
  assert(a.size() == b.size());
  HadamardTransform(a);
  HadamardTransform(b);
  for (int i = 0; i < a.size(); i++) a[i] *= b[i];
  HadamardTransform(a, true);
  return a;
}

#line 2 "set/xor-convolution.hpp"

#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;
    }
  }
}
#line 4 "set/xor-convolution.hpp"

template <class T>
vector<T> XorConvolution(vector<T> a, vector<T> b) {
  assert(a.size() == b.size());
  HadamardTransform(a);
  HadamardTransform(b);
  for (int i = 0; i < a.size(); i++) a[i] *= b[i];
  HadamardTransform(a, true);
  return a;
}