高速ゼータ変換 (fast zeta transform)
(include/emthrm/math/convolution/fast_zeta_transform.hpp)

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

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

時間計算量

$O(N\log{N})$

仕様

Yates’s algorithm

名前	戻り値
template <bool ADDS_SUPERSET, typename Ring, typename BinOp = std::plus<Ring>> std::vector<Ring> fast_zeta_transform(std::vector<Ring> a, const Ring ID = 0, const BinOp bin_op = BinOp());	$A$ に高速ゼータ変換を行ったもの	ADDS_SUPERSET は上位集合に対する変換かを表す。

参考文献

• F. Yates: The Design and Analysis of Factorial Experiments, Technical Communication, Vol. 35 (1937).
• https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5
• https://naoyat.hatenablog.jp/entry/zeta-moebius
• https://todo314.hatenadiary.org/entry/20120614/1339695202
• http://home.wakatabe.com/ryo/wiki/index.php?%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0#qef794e9
• https://lumakernel.github.io/ecasdqina/algorithm/FastZetaTransform

Submissons

https://atcoder.jp/contests/arc100/submissions/10208329

Required by

• 添え字 and での畳み込み (include/emthrm/math/convolution/and_convolution.hpp)
• 添え字 or での畳み込み (include/emthrm/math/convolution/or_convolution.hpp)

Verified with

• 数学/畳み込み/添え字 and での畳み込み (test/math/convolution/and_convolution.test.cpp)
• 数学/畳み込み/高速ゼータ変換 (test/math/convolution/fast_zeta_transform.test.cpp)

Code

#ifndef EMTHRM_MATH_CONVOLUTION_FAST_ZETA_TRANSFORM_HPP_
#define EMTHRM_MATH_CONVOLUTION_FAST_ZETA_TRANSFORM_HPP_

#include <bit>
#include <functional>
#include <vector>

namespace emthrm {

template <bool ADDS_SUPERSET, typename Ring, typename BinOp = std::plus<Ring>>
std::vector<Ring> fast_zeta_transform(
    std::vector<Ring> a, const Ring ID = 0, const BinOp bin_op = BinOp()) {
  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] = bin_op(a[s], a[s | i]);
      } else {
        a[s | i] = bin_op(a[s | i], a[s]);
      }
    }
  }
  return a;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_CONVOLUTION_FAST_ZETA_TRANSFORM_HPP_

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



#include <bit>
#include <functional>
#include <vector>

namespace emthrm {

template <bool ADDS_SUPERSET, typename Ring, typename BinOp = std::plus<Ring>>
std::vector<Ring> fast_zeta_transform(
    std::vector<Ring> a, const Ring ID = 0, const BinOp bin_op = BinOp()) {
  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] = bin_op(a[s], a[s | i]);
      } else {
        a[s | i] = bin_op(a[s | i], a[s]);
      }
    }
  }
  return a;
}

}  // namespace emthrm

Back to top page