C++ Library for Competitive Programming
#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://onlinejudge.u-aizu.ac.jp/solutions/problem/2446/review/4183902/emthrm/C++14
#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