library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:heavy_check_mark: setfunc/xor_convolution.hpp

Depends on

Verified with

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