This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/convolution/polynomial_eval_multipoint_eval.hpp"
シグネチャ
template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(std::vector<mint> &&a, const FPS<mint> &f) // (1) template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(const std::vector<mint> &a, const FPS<mint> &f) // (2)
概要
列 $A$ を変数に持つ多項式 $\displaystyle f(A)=\sum_{i=0}^{M-1} C_i \cdot A^i$ を評価します.ここで,$A^i$ はある畳み込み演算 $\ast$ に対して以下で定義されるものとします.
また,$\ast$ に対してある正則な変換行列 $\mathcal{F}$ が存在して,任意の列 $X,Y$ に対して
を満たす必要があります.ここで,$\odot$ は各点積をとる演算です.このとき,$f(A)$ は次のように計算されます.
上式における $\mathcal{F}$ と $\mathcal{F}^{-1}$ による変換を与えるのがテンプレート引数 transform および transform_inv であり,$f(\cdot)$ を評価するのが引数 f です.
transform
transform_inv
f
このライブラリでは $f(\cdot)$ たちの計算に多点評価のアルゴリズムを用いることで高速化を図ります.従って,引数として与える多項式 $f$ を形式的冪級数型 FPS に制限し,値型は atcoder::modint であることを想定しています.
FPS
atcoder::modint
テンプレート引数
mint
引数
a
返り値
$f(A)$
時間計算量
列 $A$ の長さを $N$,transform の計算量を $\Theta(f(N))$, transform_inv の計算量を $\Theta(g(N))$ として,$\Theta(f(N)+g(N)+N (\log N) ^ 2)$ です.
#ifndef SUISEN_APPLY_POLYNOMIAL_MULTIPOINT_EVAL #define SUISEN_APPLY_POLYNOMIAL_MULTIPOINT_EVAL #include "library/polynomial/multi_point_eval.hpp" #include "library/type_traits/type_traits.hpp" namespace suisen { template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(std::vector<mint> &&a, const FPS<mint> &f) { transform(a); a = multi_point_eval(f, a); transform_inv(a); return a; } template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(const std::vector<mint> &a, const FPS<mint> &f) { return polynomial_eval<mint, transform, transform_inv>(std::vector<mint>(a), f); } } // namespace suisen #endif // SUISEN_APPLY_POLYNOMIAL_MULTIPOINT_EVAL
#line 1 "library/convolution/polynomial_eval_multipoint_eval.hpp" #line 1 "library/polynomial/multi_point_eval.hpp" #include <vector> namespace suisen { template <typename FPSType, typename T> std::vector<typename FPSType::value_type> multi_point_eval(const FPSType& f, const std::vector<T>& xs) { int n = xs.size(); if (n == 0) return {}; std::vector<FPSType> seg(2 * n); for (int i = 0; i < n; ++i) seg[n + i] = FPSType{ -xs[i], 1 }; for (int i = n - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1]; seg[1] = f % seg[1]; for (int i = 2; i < 2 * n; ++i) seg[i] = seg[i / 2] % seg[i]; std::vector<typename FPSType::value_type> ys(n); for (int i = 0; i < n; ++i) ys[i] = seg[n + i].size() ? seg[n + i][0] : 0; return ys; } } // namespace suisen #line 1 "library/type_traits/type_traits.hpp" #include <limits> #include <iostream> #include <type_traits> namespace suisen { template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>; template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; }; template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; }; template <typename T> static constexpr int bitnum_v = bitnum<T>::value; template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; }; template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value; template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; }; template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type; template <typename T, typename = void> struct rec_value_type { using type = T; }; template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> { using type = typename rec_value_type<typename T::value_type>::type; }; template <typename T> using rec_value_type_t = typename rec_value_type<T>::type; template <typename T> class is_iterable { template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T> class is_writable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_writable_v = is_writable<T>::value; template <typename T> class is_readable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_readable_v = is_readable<T>::value; } // namespace suisen #line 6 "library/convolution/polynomial_eval_multipoint_eval.hpp" namespace suisen { template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(std::vector<mint> &&a, const FPS<mint> &f) { transform(a); a = multi_point_eval(f, a); transform_inv(a); return a; } template <typename mint, auto transform, auto transform_inv> std::vector<mint> polynomial_eval(const std::vector<mint> &a, const FPS<mint> &f) { return polynomial_eval<mint, transform, transform_inv>(std::vector<mint>(a), f); } } // namespace suisen