高速メビウス変換 (fast Mobius transform)
(include/emthrm/math/convolution/fast_mobius_transform.hpp)

View this file on GitHub
Last update: 2023-02-23 21:59:12+09:00
Include: #include "emthrm/math/convolution/fast_mobius_transform.hpp"

$f(S) = \sum_{S \subseteq T} (-1)^{\lvert T \setminus S \rvert} g(T)$ または $f(S) = \sum_{T \subseteq S} (-1)^{\lvert S \setminus T \rvert} g(T)$ を高速に求める。

高速ゼータ変換の逆変換と考えることができる。

時間計算量

$O(N\log{N})$

仕様

名前	戻り値	備考
`template <bool ADDS_SUPERSET, typename T>` `std::vector<T> fast_mobius_transform(std::vector<T> a, const T id = 0);`	$A$ に高速メビウス変換を行ったもの	`ADDS_SUPERSET` は上位集合に対する変換かを表す。

参考文献

https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5
https://naoyat.hatenablog.jp/entry/zeta-moebius
~~https://lumakernel.github.io/ecasdqina/algorithm/FastZetaTransform~~

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2446/review/4183902/emthrm/C++14

Required by

Verified with

Code

#ifndef EMTHRM_MATH_CONVOLUTION_FAST_MOBIUS_TRANSFORM_HPP_
#define EMTHRM_MATH_CONVOLUTION_FAST_MOBIUS_TRANSFORM_HPP_

#include <bit>
#include <vector>

namespace emthrm {

template <bool ADDS_SUPERSET, typename T>
std::vector<T> fast_mobius_transform(std::vector<T> a, const T id = 0) {
  const int n = std::bit_ceil(a.size());
  a.resize(n, id);
  for (int i = 1; i < n; i <<= 1) {
    for (int s = 0; s < n; ++s) {
      if (s & i) continue;
      if constexpr (ADDS_SUPERSET) {
        a[s] -= a[s | i];
      } else {
        a[s | i] -= a[s];
      }
    }
  }
  return a;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_CONVOLUTION_FAST_MOBIUS_TRANSFORM_HPP_

#line 1 "include/emthrm/math/convolution/fast_mobius_transform.hpp"



#include <bit>
#include <vector>

namespace emthrm {

template <bool ADDS_SUPERSET, typename T>
std::vector<T> fast_mobius_transform(std::vector<T> a, const T id = 0) {
  const int n = std::bit_ceil(a.size());
  a.resize(n, id);
  for (int i = 1; i < n; i <<= 1) {
    for (int s = 0; s < n; ++s) {
      if (s & i) continue;
      if constexpr (ADDS_SUPERSET) {
        a[s] -= a[s | i];
      } else {
        a[s | i] -= a[s];
      }
    }
  }
  return a;
}

}  // namespace emthrm

高速メビウス変換 (fast Mobius transform) (include/emthrm/math/convolution/fast_mobius_transform.hpp)