setfunc/xor_convolution.hpp

• View this file on GitHub
• Last update: 2023-10-24 20:44:29+09:00
• Include: #include "setfunc/xor_convolution.hpp"

Depends on

• setfunc/hadamard.hpp

Verified with

• test/2_library_checker/convolution/bitwise_xor_convolution.test.cpp
• test/3_yukicoder/1142.test.cpp

Code

#include "setfunc/hadamard.hpp"


template <typename T>
vc<T> xor_convolution(vc<T> A, vc<T> B) {
  hadamard(A);
  hadamard(B);
  FOR(i, len(A)) A[i] *= B[i];
  hadamard(A);

  T c = T(1) / T(len(A));
  if (c != T(0)) {
    FOR(i, len(A)) A[i] *= c;
  } else {
    FOR(i, len(A)) A[i] /= len(A);
  }
  return A;
}

#line 2 "setfunc/hadamard.hpp"

// B[j] = sum_i (-1)^{popcnt(i&j)A[i]}

// 2^n で割ることはしていない

template <typename T>
void hadamard(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s < t) tie(A[s], A[t]) = mp(A[s] + A[t], A[s] - A[t]);
  }
}
#line 2 "setfunc/xor_convolution.hpp"

template <typename T>
vc<T> xor_convolution(vc<T> A, vc<T> B) {
  hadamard(A);
  hadamard(B);
  FOR(i, len(A)) A[i] *= B[i];
  hadamard(A);

  T c = T(1) / T(len(A));
  if (c != T(0)) {
    FOR(i, len(A)) A[i] *= c;
  } else {
    FOR(i, len(A)) A[i] /= len(A);
  }
  return A;
}

Back to top page