C++ Library for Competitive Programming
#include "emthrm/math/convolution/exp_of_set_power_series.hpp"
集合冪級数 $(\lbrace f \in 2^{\lbrack n \rbrack} \to K \rbrace, +, \ast)$ を考える。$f(\emptyset) = 0$ を満たす $f \in 2^{\lbrack n \rbrack} \to K$ に対して
\[\exp{f} \mathrel{:=} \sum_{k = 0}^\infty \frac{f^k}{k!}\]で定義される $\exp$ である。
$O(2^N N^2)$
名前 | 戻り値 | 要件 |
---|---|---|
template <int MaxN, typename T> std::vector<T> exp_of_set_power_series(const std::vector<T>& f);
|
$\exp{f}$ | $n \leq \mathrm{MaxN}$ $f(\emptyset) = 0$ |
https://judge.yosupo.jp/problem/exp_of_set_power_series
#ifndef EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_
#define EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_
#include <algorithm>
#include <bit>
#include <cassert>
#include <iterator>
#include <vector>
#include "emthrm/math/convolution/subset_convolution.hpp"
namespace emthrm {
template <int MaxN, typename T>
std::vector<T> exp_of_set_power_series(const std::vector<T>& f) {
assert(std::has_single_bit(f.size()) && f[0] == 0);
const int n = std::countr_zero(f.size());
assert(n <= MaxN);
std::vector<T> exponential{1};
exponential.reserve(1 << n);
for (int i = 0; i < n; ++i) {
std::ranges::copy(subset_convolution<MaxN>(
exponential,
std::vector(std::next(f.begin(), 1 << i),
std::next(f.begin(), 1 << (i + 1)))),
std::back_inserter(exponential));
}
return exponential;
}
} // namespace emthrm
#endif // EMTHRM_MATH_CONVOLUTION_EXP_OF_SET_POWER_SERIES_HPP_
#line 1 "include/emthrm/math/convolution/exp_of_set_power_series.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <iterator>
#include <vector>
#line 1 "include/emthrm/math/convolution/subset_convolution.hpp"
#include <array>
#line 7 "include/emthrm/math/convolution/subset_convolution.hpp"
#include <utility>
#line 9 "include/emthrm/math/convolution/subset_convolution.hpp"
namespace emthrm {
template <int MaxN, typename T>
std::vector<T> subset_convolution(
const std::vector<T>& f, const std::vector<T>& g) {
using Polynomial = std::array<T, MaxN + 1>;
assert(std::has_single_bit(f.size()) && f.size() == g.size());
const int n = std::countr_zero(f.size());
assert(n <= MaxN);
const int domain_size = 1 << n;
const auto ranked_zeta_transform =
[n, domain_size](const std::vector<T>& f) -> std::vector<Polynomial> {
std::vector a(domain_size, Polynomial{});
for (int i = 0; i < domain_size; ++i) {
a[i][std::popcount(static_cast<unsigned int>(i))] = f[i];
}
for (int bit = 1; bit < domain_size; bit <<= 1) {
for (int i = 0; i < domain_size; ++i) {
if ((i & bit) == 0) {
for (int degree = 0; degree <= n; ++degree) {
a[i | bit][degree] += a[i][degree];
}
}
}
}
return a;
};
std::vector<Polynomial> a = ranked_zeta_transform(f);
const std::vector<Polynomial> b = ranked_zeta_transform(g);
for (int i = 0; i < domain_size; ++i) {
// Hadamard product
for (int degree_of_a = n; degree_of_a >= 0; --degree_of_a) {
const T tmp = std::exchange(a[i][degree_of_a], T{});
for (int degree_of_b = 0; degree_of_a + degree_of_b <= n; ++degree_of_b) {
a[i][degree_of_a + degree_of_b] += tmp * b[i][degree_of_b];
}
}
}
for (int bit = 1; bit < domain_size; bit <<= 1) {
for (int i = 0; i < domain_size; ++i) {
if ((i & bit) == 0) {
for (int degree = 0; degree <= n; ++degree) {
a[i | bit][degree] -= a[i][degree];
}
}
}
}
std::vector<T> c(domain_size);
for (int i = 0; i < domain_size; ++i) {
c[i] = a[i][std::popcount(static_cast<unsigned int>(i))];
}
return c;
}
} // namespace emthrm
#line 11 "include/emthrm/math/convolution/exp_of_set_power_series.hpp"
namespace emthrm {
template <int MaxN, typename T>
std::vector<T> exp_of_set_power_series(const std::vector<T>& f) {
assert(std::has_single_bit(f.size()) && f[0] == 0);
const int n = std::countr_zero(f.size());
assert(n <= MaxN);
std::vector<T> exponential{1};
exponential.reserve(1 << n);
for (int i = 0; i < n; ++i) {
std::ranges::copy(subset_convolution<MaxN>(
exponential,
std::vector(std::next(f.begin(), 1 << i),
std::next(f.begin(), 1 << (i + 1)))),
std::back_inserter(exponential));
}
return exponential;
}
} // namespace emthrm