setfunc/and_convolution.hpp

View this file on GitHub
Last update: 2025-05-25 23:45:10+09:00
Include: #include "setfunc/and_convolution.hpp"

Depends on

setfunc/zeta.hpp

Verified with

test/2_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 n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] += a[i + j + k];
}

template <typename T>
void superset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] -= a[i + j + k];
}

template <typename T>
void subset_zeta(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] += a[j + k];
}

template <typename T>
void subset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] -= a[j + k];
}
#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;
}