Bitwise AND Convolution
(math/set-function/BitwiseANDConvolution.hpp)

• View this file on GitHub
• Last update: 2026-04-18 20:38:59+09:00
• Include: #include "math/set-function/BitwiseANDConvolution.hpp"

概要

todo

計算量

todo

Depends on

• Superset/Subset Zeta/Möbius Transform (math/set-function/ZetaMobiusTransform.hpp)

Verified with

• verify/LibraryChecker/math/set-function/BitwiseANDConvolution.test.cpp

Code

#include "ZetaMobiusTransform.hpp"

template <class T>
vector<T> and_convolution(int n, vector<T> a, vector<T> b) {
  vector<T> za = superset_zeta(n, a);
  vector<T> zb = superset_zeta(n, b);
  vector<T> d(1 << n);
  for (int i = 0; i < (1 << n); i++) d[i] = za[i] * zb[i];
  return superset_mobius(n, d);
}

#line 1 "math/set-function/ZetaMobiusTransform.hpp"

template <class T>
vector<T> subset_zeta(int n, vector<T> a) {
  for (int i = 0; i < n; i++) {
    for (int t = 0; t < (1 << n); t++) {
      if (t & (1 << i)) a[t] += a[t ^ (1 << i)];
    }
  }
  return a;
}

template <class T>
vector<T> subset_mobius(int n, vector<T> a) {
  for (int i = 0; i < n; i++) {
    for (int t = 0; t < (1 << n); t++) {
      if (t & (1 << i)) a[t] -= a[t ^ (1 << i)];
    }
  }
  return a;
}

template <class T>
vector<T> superset_zeta(int n, vector<T> a) {
  for (int i = 0; i < n; i++) {
    for (int t = 0; t < (1 << n); t++) {
      if (!(t & (1 << i))) a[t] += a[t | (1 << i)];
    }
  }
  return a;
}

template <class T>
vector<T> superset_mobius(int n, vector<T> a) {
  for (int i = 0; i < n; i++) {
    for (int t = 0; t < (1 << n); t++) {
      if (!(t & (1 << i))) a[t] -= a[t | (1 << i)];
    }
  }
  return a;
}
#line 2 "math/set-function/BitwiseANDConvolution.hpp"

template <class T>
vector<T> and_convolution(int n, vector<T> a, vector<T> b) {
  vector<T> za = superset_zeta(n, a);
  vector<T> zb = superset_zeta(n, b);
  vector<T> d(1 << n);
  for (int i = 0; i < (1 << n); i++) d[i] = za[i] * zb[i];
  return superset_mobius(n, d);
}

Back to top page