setfunc/hadamard.hpp

• View this file on GitHub
• Last update: 2023-09-18 22:09:51+09:00
• Include: #include "setfunc/hadamard.hpp"

Required by

• setfunc/xor_convolution.hpp

Verified with

• test/library_checker/convolution/bitwise_xor_convolution.test.cpp
• test/yukicoder/1142.test.cpp
• test/yukicoder/1753.test.cpp
• test_atcoder/abc212h.test.cpp

Code

#pragma once

// 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/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]);
  }
}

Back to top page