set/zeta-mobius-transform.hpp

• View this file on GitHub
• Last update: 2025-10-29 02:30:28+09:00
• Include: #include "set/zeta-mobius-transform.hpp"

Required by

• set/and-convolution.hpp
• set/or-convolution.hpp

Verified with

• verify/set/LC_bitwise_and_convolution.or.test.cpp
• verify/set/LC_bitwise_and_convolution.test.cpp

Code

#pragma once

template <class T>
void SupsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] += f[i + j + k];
}

template <class T>
void SupsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] -= f[i + j + k];
}

template <class T>
void SubsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] += f[j + k];
}

template <class T>
void SubsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] -= f[j + k];
}

#line 2 "set/zeta-mobius-transform.hpp"

template <class T>
void SupsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] += f[i + j + k];
}

template <class T>
void SupsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[j + k] -= f[i + j + k];
}

template <class T>
void SubsetZetaTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] += f[j + k];
}

template <class T>
void SubsetMobiusTransform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i * 2)
      for (int k = 0; k < i; k++)
        f[i + j + k] -= f[j + k];
}

Back to top page