setfunc/and_convolution.hpp

View this file on GitHub
Last update: 2022-04-16 04:26:49+09:00
Include: #include "setfunc/and_convolution.hpp"

Depends on

setfunc/zeta.hpp

Verified with

test/library_checker/convolution/bitwise_and_convolution.test.cpp

Code

#include "setfunc/zeta.hpp"
template <typename T>
vc<T> and_convolution(vc<T> A, vc<T> B) {
  superset_zeta(A);
  superset_zeta(B);
  FOR(i, len(A)) A[i] *= B[i];
  superset_mobius(A);
  return A;
}

#line 2 "setfunc/zeta.hpp"

template <typename T>
void superset_zeta(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) A[s] += A[t];
  }
}

template <typename T>
void superset_mobius(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) A[s] -= A[t];
  }
}

template <typename T>
void subset_zeta(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) A[s] += A[t];
  }
}

template <typename T>
void subset_mobius(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) A[s] -= A[t];
  }
}
#line 2 "setfunc/and_convolution.hpp"
template <typename T>
vc<T> and_convolution(vc<T> A, vc<T> B) {
  superset_zeta(A);
  superset_zeta(B);
  FOR(i, len(A)) A[i] *= B[i];
  superset_mobius(A);
  return A;
}