Submit Info #52263

Problem Lang User Status Time Memory
Multipoint Evaluation cpp-acl Forested AC 851 ms 25.11 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.58 MiB
example_01 AC 1 ms 0.71 MiB
max_random_00 AC 851 ms 24.69 MiB
max_random_01 AC 849 ms 24.68 MiB
random_00 AC 159 ms 8.90 MiB
random_01 AC 142 ms 7.21 MiB
random_02 AC 780 ms 25.11 MiB

// ----- "multipoint_evaluation.hpp" ----- #ifndef MULTIPOINT_EVALUATION_HPP #define MULTIPOINT_EVALUATION_HPP // ----- "polynomial.hpp" ----- #ifndef POLYNOMIAL_HPP #define POLYNOMIAL_HPP #include <vector> #include <cassert> #include <utility> #include <algorithm> // ----- "formal_power_series.hpp" ----- #ifndef FORMAL_POWER_SERIES_HPP #define FORMAL_POWER_SERIES_HPP #include <vector> #include <utility> #include <cassert> namespace math { template <typename T, typename Mul = void> class FormalPowerSeries { std::vector<T> coeff; public: using This = FormalPowerSeries<T, Mul>; FormalPowerSeries() : coeff() {} FormalPowerSeries(std::size_t n) : coeff(n) {} FormalPowerSeries(const std::vector<T> &vec) : coeff(vec) {} FormalPowerSeries(std::vector<T> &&vec) : coeff(std::move(vec)) {} std::vector<T> vec() const { return coeff; } std::size_t size() const { return coeff.size(); } void resize(std::size_t n) { coeff.resize(n); } const T &operator[](std::size_t idx) const { return coeff[idx]; } T &operator[](std::size_t idx) { return coeff[idx]; } This operator+() const { return *this; } This operator-() const { This ret; ret.coeff.reserve(coeff.size()); for (const T &ele : coeff) { ret.coeff.push_back(-ele); } return ret; } This &operator+=(const This &rhs) { assert(coeff.size() == rhs.coeff.size()); for (std::size_t i = 0; i < size(); ++i) { coeff[i] += rhs.coeff[i]; } return *this; } friend This operator+(This lhs, const This &rhs) { return lhs += rhs; } This &operator-=(const This &rhs) { assert(coeff.size() == rhs.coeff.size()); for (std::size_t i = 0; i < size(); ++i) { coeff[i] -= rhs.coeff[i]; } return *this; } friend This operator-(This lhs, const This &rhs) { return lhs -= rhs; } This &operator*=(This rhs) { assert(coeff.size() == rhs.coeff.size()); std::size_t sz = coeff.size(); std::vector<T> other; coeff.swap(other); coeff = Mul::mul(std::move(other), std::move(rhs.coeff)); coeff.resize(sz); return *this; } // ? friend This operator*(This lhs, This rhs) { return lhs *= rhs; } private: This inv_naive() const { assert(!coeff.empty()); std::vector<T> ret({T(1) / coeff[0]}); while (ret.size() < coeff.size()) { std::vector<T> tmp = Mul::mul(coeff, Mul::mul(ret, ret)); ret.resize(ret.size() * 2); for (std::size_t i = 0; i < ret.size(); ++i) { ret[i] = 2 * ret[i] - tmp[i]; } } ret.resize(coeff.size()); return This(std::move(ret)); } This inv_fast() const { assert(!coeff.empty()); std::vector<T> ret({T(1) / coeff[0]}); while (ret.size() < coeff.size()) { std::size_t sz = ret.size(); std::vector<T> _coeff = coeff; _coeff.resize(sz * 2); Mul::dft(_coeff); std::vector<T> _ret = ret; _ret.resize(sz * 2); Mul::dft(_ret); for (std::size_t i = 0; i < sz * 2; ++i) { _coeff[i] *= _ret[i]; } Mul::idft(_coeff); for (std::size_t i = 0; i < sz; ++i) { _coeff[i] = T(0); } Mul::dft(_coeff); for (std::size_t i = 0; i < sz * 2; ++i) { _coeff[i] *= _ret[i]; } Mul::idft(_coeff); ret.resize(sz * 2); for (std::size_t i = sz; i < sz * 2; ++i) { ret[i] -= _coeff[i]; } } ret.resize(coeff.size()); return This(std::move(ret)); } public: This inv() const { if constexpr (Mul::has_dft) { return inv_fast(); } else { return inv_naive(); } } This operator/=(const This &rhs) { return *this *= rhs.inv(); } friend This operator/(This lhs, const This &rhs) { return lhs *= rhs.inv(); } }; template <typename T> struct Naive { static constexpr bool has_dft = false; static std::vector<T> mul(const std::vector<T> &lhs, const std::vector<T> &rhs) { if (lhs.empty() || rhs.empty()) { return std::vector<T>(); } std::vector<T> ret(lhs.size() + rhs.size() - 1, T(0)); for (std::size_t i = 0; i < lhs.size(); ++i) { for (std::size_t j = 0; j < rhs.size(); ++j) { ret[i + j] += lhs[i] * rhs[j]; } } return ret; } }; } // namespace math #endif // ----- "formal_power_series.hpp" ----- namespace math { template <typename T, typename Mul> class Polynomial { std::vector<T> coeff; public: using This = Polynomial<T, Mul>; Polynomial() : coeff(0) {} Polynomial(std::size_t n) : coeff(n) {} Polynomial(const std::vector<T> &vec) : coeff(vec) {} Polynomial(std::vector<T> &&vec) : coeff(std::move(vec)) {} Polynomial(const This &other) : coeff(other.coeff) {} Polynomial(This &&other) : coeff(std::move(other.coeff)) {} This &operator=(const This &other) { coeff = other.coeff; return *this; } This &operator=(This &&other) { coeff = std::move(other.coeff); return *this; } std::size_t size() const { return coeff.size(); } std::size_t deg() const { if (coeff.empty()) { return 0; } for (std::size_t i = coeff.size() - 1; i <= coeff.size(); --i) { if (coeff[i] != T(0)) { return i; } } } std::size_t resize(std::size_t n) { coeff.resize(n); } void shrink() { while (!coeff.empty() && coeff.back() == T(0)) { coeff.pop_back(); } } const T &operator[](std::size_t idx) const { assert(idx < coeff.size()); return coeff[idx]; } T &operator[](std::size_t idx) { assert(idx < coeff.size()); return coeff[idx]; } T operator()(const T &x) const { T p(1), ret(0); for (const T &c : coeff) { ret += c * p; p *= x; } return ret; } This operator+() const { return *this; } This operator-() const { This ret; ret.coeff.reserve(coeff.size()); for (const T &ele : coeff) { ret.coeff.push_back(-ele); } return ret; } This &operator+=(const This &rhs) { if (coeff.size() < rhs.coeff.size()) { coeff.resize(rhs.coeff.size(), T(0)); } for (std::size_t i = 0; i < rhs.coeff.size(); ++i) { coeff[i] += rhs.coeff[i]; } return *this; } friend This operator+(This lhs, const This &rhs) { return lhs += rhs; } This &operator-=(const This &rhs) { if (coeff.size() < rhs.coeff.size()) { coeff.resize(rhs.coeff.size(), T(0)); } for (std::size_t i = 0; i < rhs.coeff.size(); ++i) { coeff[i] -= rhs.coeff[i]; } return *this; } friend This operator-(This lhs, const This &rhs) { return lhs -= rhs; } This &operator*=(This rhs) { coeff = Mul::mul(std::move(coeff), std::move(rhs.coeff)); return *this; } friend This operator*(This lhs, This rhs) { return lhs *= std::move(rhs); } This &operator/=(This rhs) { assert(!rhs.coeff.empty()); if (coeff.size() < rhs.coeff.size()) { coeff.resize(0); return *this; } std::size_t n = coeff.size() - rhs.coeff.size() + 1; std::reverse(coeff.begin(), coeff.end()); coeff.resize(n); std::reverse(rhs.coeff.begin(), rhs.coeff.end()); rhs.coeff.resize(n, T(0)); FormalPowerSeries<T, Mul> l(std::move(coeff)); FormalPowerSeries<T, Mul> r(std::move(rhs.coeff)); l /= std::move(r); coeff = l.vec(); std::reverse(coeff.begin(), coeff.end()); return *this; } friend This operator/(This lhs, This rhs) { return lhs /= std::move(rhs); } This &operator%=(This rhs) { *this -= *this / rhs * rhs; coeff.resize(rhs.size() - 1); return *this; } friend This operator%(This lhs, This rhs) { return lhs %= std::move(rhs); } }; } // namespace math #endif // ----- "polynomial.hpp" ----- namespace math { std::size_t ceil2(std::size_t n) { std::size_t ret = 1; while (ret < n) ret <<= 1; return ret; } template <typename T, typename Mul> std::vector<T> multipoint_evaluation(Polynomial<T, Mul> f, const std::vector<T> &x) { using Poly = Polynomial<T, Mul>; if (x.empty()) return std::vector<T>(); std::size_t n = ceil2(x.size()); std::vector<Poly> prod(n << 1, Poly(std::vector<T>{T(1)})); for (std::size_t i = 0; i < x.size(); ++i) prod[i + n] = Poly(std::vector<T>{-x[i], T(1)}); for (std::size_t i = n - 1; i > 0; --i) { prod[i] = prod[i << 1] * prod[(i << 1) | 1]; } prod[1] = std::move(f) % std::move(prod[1]); for (std::size_t i = 2; i < n + x.size(); ++i) prod[i] = prod[i >> 1] % std::move(prod[i]); std::vector<T> ret(x.size()); for (std::size_t i = 0; i < x.size(); ++i) ret[i] = prod[i + n][0]; return ret; } } // namespace math #endif // ----- "multipoint_evaluation.hpp" ----- #include "atcoder/convolution" #include <iostream> using Mint = atcoder::modint998244353; class NTTMul { public: static constexpr bool has_dft = true; static void dft(std::vector<Mint> &a) { atcoder::internal::butterfly(a); } static void idft(std::vector<Mint> &a) { atcoder::internal::butterfly_inv(a); Mint inv = Mint::raw(a.size()).inv(); for (Mint &ele : a) { ele *= inv; } } static std::vector<Mint> mul(std::vector<Mint> lhs, std::vector<Mint> rhs) { return atcoder::convolution(std::move(lhs), std::move(rhs)); } }; using Poly = math::Polynomial<Mint, NTTMul>; int main() { // set up io std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::size_t n, m; std::cin >> n >> m; Poly f(n); for (std::size_t i = 0; i < n; ++i) { unsigned v; std::cin >> v; f[i] = Mint::raw(v); } std::vector<Mint> xs(m); for (std::size_t i = 0; i < m; ++i) { unsigned v; std::cin >> v; xs[i] = Mint::raw(v); } std::vector<Mint> res = multipoint_evaluation(std::move(f), xs); for (std::size_t i = 0; i < m; ++i) { std::cout << res[i].val(); if (i + 1 == m) { std::cout << '\n'; } else { std::cout << ' '; } } }