setfunc/zeta.hpp

• View this file on GitHub
• Last update: 2025-05-25 23:45:10+09:00
• Include: #include "setfunc/zeta.hpp"

Required by

• setfunc/and_convolution.hpp
• setfunc/or_convolution.hpp

Verified with

• test/2_library_checker/convolution/bitwise_and_convolution.test.cpp
• test/2_library_checker/convolution/bitwise_or_convolution.test.cpp

Code

#pragma once

template <typename T>
void superset_zeta(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] += a[i + j + k];
}

template <typename T>
void superset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] -= a[i + j + k];
}

template <typename T>
void subset_zeta(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] += a[j + k];
}

template <typename T>
void subset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] -= a[j + k];
}

#line 2 "setfunc/zeta.hpp"

template <typename T>
void superset_zeta(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] += a[i + j + k];
}

template <typename T>
void superset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[j + k] -= a[i + j + k];
}

template <typename T>
void subset_zeta(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] += a[j + k];
}

template <typename T>
void subset_mobius(vc<T>& a) {
  int n = len(a);
  for (int i = 1; i != n; i <<= 1)
    for (int j = 0; j != n; j += i << 1)
      for (int k = 0; k != i; k++) a[i + j + k] -= a[j + k];
}

Back to top page