Bitwise OR Convolution
(math/set-function/BitwiseORConvolution.hpp)

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

概要

todo

計算量

todo

Depends on

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

Code

#include "ZetaMobiusTransform.hpp"

template <class T>
vector<T> or_convolution(int n, vector<T> a, vector<T> b) {
  vector<T> za = subset_zeta(n, a);
  vector<T> zb = subset_zeta(n, b);
  vector<T> d(1 << n);
  for (int i = 0; i < (1 << n); i++) d[i] = za[i] * zb[i];
  return subset_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/BitwiseORConvolution.hpp"

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

Back to top page