cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: 列を変数として持つ多項式の評価 (多点評価版)
(library/convolution/polynomial_eval_multipoint_eval.hpp)

polynomial_eval

Depends on

Verified with

Code

#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
Back to top page