setfunc/zeta.hpp

• View this file on GitHub
• Last update: 2022-04-16 04:26:49+09:00
• Include: #include "setfunc/zeta.hpp"
• Link: View error logs on GitHub Actions

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
• test/5_atcoder/arc105.test.cpp

Code

#pragma once

template <typename T>
void superset_zeta(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s < t) A[s] += A[t];
  }
}

template <typename T>
void superset_mobius(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s < t) A[s] -= A[t];
  }
}

template <typename T>
void subset_zeta(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s > t) A[s] += A[t];
  }
}

template <typename T>
void subset_mobius(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s > t) A[s] -= A[t];
  }
}

#line 2 "setfunc/zeta.hpp"

template <typename T>
void superset_zeta(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s < t) A[s] += A[t];
  }
}

template <typename T>
void superset_mobius(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s < t) A[s] -= A[t];
  }
}

template <typename T>
void subset_zeta(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s > t) A[s] += A[t];
  }
}

template <typename T>
void subset_mobius(vc<T>& A) {
  int log = topbit(len(A));
  assert(1 << log == len(A));
  FOR(n, log) FOR(s, 1 << log) {
    int t = s ^ (1 << n);
    if (s > t) A[s] -= A[t];
  }
}

Back to top page