math/convolution/and-convolution.hpp

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "math/convolution/and-convolution.hpp"

Verified with

• test/yosupo/Convolution/Bitwise-And-Convolution.test.cpp

Code

template <class T>
void fzt(vector<T> &a){
  const int n = a.size();
  for(int j = 0; (1 << j) < n; j++){
    for(int i = 0; i < n; i++){
      if(!(i >> j & 1)) a[i] += a[i | 1 << j];
    }
  }
}
template <class T>
void fmt(vector<T> &a){
  const int n = a.size();
  for(int j = 0; (1 << j) < n; j++){
    for(int i = 0; i < n; i++){
      if(!(i >> j & 1)) a[i] -= a[i | 1 << j];
    }
  }
}
template <class T>
vector<T> and_convolution(vector<T> a, vector<T> b){
  const int n = a.size();
  assert((n & (n - 1)) == 0 && a.size() == b.size());
  fzt(a);
  fzt(b);
  vector<T> c(n);
  for(int i = 0; i < n; i++) c[i] = a[i] * b[i];
  fmt(c);
  return c;
}

#line 1 "math/convolution/and-convolution.hpp"
template <class T>
void fzt(vector<T> &a){
  const int n = a.size();
  for(int j = 0; (1 << j) < n; j++){
    for(int i = 0; i < n; i++){
      if(!(i >> j & 1)) a[i] += a[i | 1 << j];
    }
  }
}
template <class T>
void fmt(vector<T> &a){
  const int n = a.size();
  for(int j = 0; (1 << j) < n; j++){
    for(int i = 0; i < n; i++){
      if(!(i >> j & 1)) a[i] -= a[i | 1 << j];
    }
  }
}
template <class T>
vector<T> and_convolution(vector<T> a, vector<T> b){
  const int n = a.size();
  assert((n & (n - 1)) == 0 && a.size() == b.size());
  fzt(a);
  fzt(b);
  vector<T> c(n);
  for(int i = 0; i < n; i++) c[i] = a[i] * b[i];
  fmt(c);
  return c;
}

Back to top page