上位集合についての高速ゼータ変換/メビウス変換
(convolution/superset-zeta-moebius-transform.hpp)

• View this file on GitHub
• Last update: 2024-06-20 21:09:39+09:00
• Include: #include "convolution/superset-zeta-moebius-transform.hpp"

概要

可換な二項演算(大抵の場合、数の和) $\oplus$ があるとき、 サイズ$N$の集合 $S$について、$f(S)$が($2^N$のvectorで)与えられたときに、 $ g(S) = \bigoplus_{S \subseteq T} f(T) $ を求めたり(Zeta)、その逆変換を求めたり(Möbius)する。

添字AND畳み込みは、上位集合についてゼータ変換したあとに各点積を取ってメビウス変換すると求められたりする。

Scrapboxを見るといっぱい資料がある。

計算量

ゼータもメビウスも

• $O(N 2^N ) $

Verified with

• test/verify/convolution/yosupo-and-convolution.test.cpp

Code

#ifndef HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP
#define HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP

#include <vector>

template <class T, T (*op)(T, T) >
std::vector<T> superset_zeta_transform(const std::vector<T>& f) {

  int n = 0; while ((1 << n) < (int)f.size()) n++;
  assert((int)f.size() == (1 << n)); // f.size() should be power of 2.


  std::vector<T> F = f;
  for (int k = 0; k < n; k++) {
    for (int s = 0; s < 1 << n; s++) {
      if (!((s >> k) & 1)) F[s] = op(F[s], F[s ^ (1 << k)]);
    }
  }
  return F;
}


template <class T, T (*invop)(T, T) >
std::vector<T> superset_moebius_transform(const std::vector<T>& f) {
  int n = 0; while ((1 << n) < (int)f.size()) n++;
  assert((int)f.size() == (1 << n)); // f.size() should be power of 2.

  std::vector<T> F = f;
  for (int k = 0; k < n; k++) {
    for (int s = 0; s < 1 << n; s++) {
      if (!((s >> k) & 1)) F[s] = invop(F[s], F[s ^ (1 << k)]);
    }
  }
  return F;
}

#endif // HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP

#line 1 "convolution/superset-zeta-moebius-transform.hpp"



#include <vector>

template <class T, T (*op)(T, T) >
std::vector<T> superset_zeta_transform(const std::vector<T>& f) {

  int n = 0; while ((1 << n) < (int)f.size()) n++;
  assert((int)f.size() == (1 << n)); // f.size() should be power of 2.


  std::vector<T> F = f;
  for (int k = 0; k < n; k++) {
    for (int s = 0; s < 1 << n; s++) {
      if (!((s >> k) & 1)) F[s] = op(F[s], F[s ^ (1 << k)]);
    }
  }
  return F;
}


template <class T, T (*invop)(T, T) >
std::vector<T> superset_moebius_transform(const std::vector<T>& f) {
  int n = 0; while ((1 << n) < (int)f.size()) n++;
  assert((int)f.size() == (1 << n)); // f.size() should be power of 2.

  std::vector<T> F = f;
  for (int k = 0; k < n; k++) {
    for (int s = 0; s < 1 << n; s++) {
      if (!((s >> k) & 1)) F[s] = invop(F[s], F[s ^ (1 << k)]);
    }
  }
  return F;
}

Back to top page