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

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

概要

todo

計算量

todo

Required by

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

Verified with

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

Code

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 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;
}

Back to top page