set/and-convolution.hpp

View this file on GitHub
Last update: 2025-10-29 02:30:28+09:00
Include: #include "set/and-convolution.hpp"

Depends on

set/zeta-mobius-transform.hpp

Verified with

verify/set/LC_bitwise_and_convolution.test.cpp

Code

#pragma once

#include "./zeta-mobius-transform.hpp"

template <class T>
vector<T> AndConvolution(vector<T> a, vector<T> b) {
  assert(a.size() == b.size());
  SupsetZetaTransform(a);
  SupsetZetaTransform(b);
  for (int i = 0; i < a.size(); i++) a[i] *= b[i];
  SupsetMobiusTransform(a);
  return a;
}

#line 2 "set/and-convolution.hpp"

#line 2 "set/zeta-mobius-transform.hpp"

template <class T>
void SupsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] += f[i + j + k];
}

template <class T>
void SupsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] -= f[i + j + k];
}

template <class T>
void SubsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] += f[j + k];
}

template <class T>
void SubsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] -= f[j + k];
}
#line 4 "set/and-convolution.hpp"

template <class T>
vector<T> AndConvolution(vector<T> a, vector<T> b) {
  assert(a.size() == b.size());
  SupsetZetaTransform(a);
  SupsetZetaTransform(b);
  for (int i = 0; i < a.size(); i++) a[i] *= b[i];
  SupsetMobiusTransform(a);
  return a;
}