Submit Info #52260

Problem Lang User Status Time Memory
Multipoint Evaluation cpp Forested AC 1495 ms 26.03 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.71 MiB
max_random_00 AC 1495 ms 25.92 MiB
max_random_01 AC 1495 ms 26.03 MiB
random_00 AC 255 ms 8.91 MiB
random_01 AC 232 ms 7.21 MiB
random_02 AC 1332 ms 25.12 MiB

// ----- "number_theoretic_transform.hpp" ----- #ifndef NUMBER_THEORETIC_TRANSFORM #define NUMBER_THEORETIC_TRANSFORM // ----- "mod_int.hpp" ----- #ifndef MOD_INT_HPP #define MOD_INT_HPP #include <cassert> #include <type_traits> #include <iostream> // ----- "utils.hpp" ----- #ifndef UTILS_HPP #define UTILS_HPP #include <cstddef> namespace math { constexpr bool is_prime(unsigned n) { if (n == 0 || n == 1) return false; for (unsigned i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) { unsigned ret = 1, self = x; while (y != 0) { if (y & 1) ret = (unsigned long long) ret * self % mod; self = (unsigned long long) self * self % mod; y >>= 1; } return ret; } template <unsigned mod> constexpr unsigned primitive_root() { static_assert(is_prime(mod), "`mod` must be a prime number."); if (mod == 2) return 1; unsigned primes[32] = {}; std::size_t it = 0; { unsigned m = mod - 1; for (unsigned i = 2; i * i <= m; ++i) { if (m % i == 0) { primes[it++] = i; while (m % i == 0) m /= i; } } if (m != 1) primes[it++] = m; } for (unsigned i = 2; i < mod; ++i) { bool ok = true; for (std::size_t j = 0; j < it; ++j) { if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) { ok = false; break; } } if (ok) return i; } return 0; } } // namespace math #endif // ----- "utils.hpp" ----- namespace math { template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr> unsigned safe_mod(T x, unsigned mod) { if (x < 0) { return (unsigned) (x % mod + mod); } else { return (unsigned) (x % mod); } } template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr> unsigned safe_mod(T x, unsigned mod) { return (unsigned) (x % mod); } template <unsigned mod> class ModInt { static_assert(mod != 0, "`mod` must not be equal to 0."); static_assert(mod < (1u << 31), "`mod` must be less than (1u << 31) = 2147483648."); unsigned val; public: constexpr ModInt() : val(0) {} template <typename T> constexpr ModInt(T x) : val(safe_mod(x, mod)) {} static constexpr ModInt raw(unsigned x) { ModInt<mod> ret; ret.val = x; return ret; } constexpr unsigned get_val() const { return val; } constexpr ModInt operator+() const { return *this; } constexpr ModInt operator-() const { return ModInt<mod>(0u) - *this; } constexpr ModInt &operator+=(const ModInt &rhs) { val += rhs.val; if (val >= mod) val -= mod; return *this; } constexpr ModInt &operator-=(const ModInt &rhs) { if (val < rhs.val) val += mod; val -= rhs.val; return *this; } constexpr ModInt &operator*=(const ModInt &rhs) { val = (unsigned long long) val * rhs.val % mod; return *this; } constexpr ModInt &operator/=(const ModInt &rhs) { val = (unsigned long long) val * rhs.inv().val % mod; return *this; } friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) += rhs; } friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) -= rhs; } friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) *= rhs; } friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) /= rhs; } constexpr ModInt pow(unsigned x) const { ModInt<mod> ret = ModInt<mod>::raw(1); ModInt<mod> self = *this; while (x != 0) { if (x & 1) ret *= self; self *= self; x >>= 1; } return ret; } constexpr ModInt inv() const { static_assert(is_prime(mod), "`mod` must be a prime number."); assert(val != 0); return this->pow(mod - 2); } friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) { is >> x.val; // x.val %= mod; return is; } friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) { os << x.val; return os; } friend bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val == rhs.val; } }; } // namespace math #endif // ----- "mod_int.hpp" ----- #include <vector> #include <array> namespace math { template <unsigned mod> class NumberTheoreticTransform { static constexpr std::size_t calc_ex() { unsigned m = mod - 1; std::size_t ret = 0; while (!(m & 1)) { m >>= 1; ++ret; } return ret; } static constexpr std::size_t max_ex = calc_ex(); std::array<ModInt<mod>, max_ex + 1> root, inv_root; inline std::size_t ctz(std::size_t n) const { return __builtin_ctzl(n); } public: void dft(std::vector<ModInt<mod>> &a) const { std::size_t n = a.size(); std::size_t ex = ctz(n); std::size_t m = n; while (m > 1) { for (std::size_t s = 0; s < n; s += m) { auto z = ModInt<mod>::raw(1); for (std::size_t i = 0; i < m >> 1; ++i) { auto x = a[s + i]; auto y = a[s + i + m / 2]; a[s + i] = x + y; a[s + i + m / 2] = (x - y) * z; z *= root[ex]; } } m >>= 1; --ex; } } void idft(std::vector<ModInt<mod>> &a) const { std::size_t n = a.size(); std::size_t m = 2; std::size_t ex = 1; while (m <= n) { for (std::size_t s = 0; s < n; s += m) { auto z = ModInt<mod>::raw(1); for (std::size_t i = 0; i < m / 2; ++i) { auto x = a[s + i]; auto y = a[s + i + m / 2] * z; a[s + i] = x + y; a[s + i + m / 2] = x - y; z *= inv_root[ex]; } } m <<= 1; ++ex; } ModInt<mod> inv = ModInt<mod>::raw(a.size()).inv(); for (ModInt<mod> &ele : a) ele *= inv; } constexpr NumberTheoreticTransform() : root(), inv_root() { ModInt<mod> g = ModInt<mod>::raw(primitive_root<mod>()).pow((mod - 1) >> max_ex); root[max_ex] = g; inv_root[max_ex] = g.inv(); for (std::size_t i = max_ex; i > 0; --i) { root[i - 1] = root[i] * root[i]; inv_root[i - 1] = inv_root[i] * inv_root[i]; } } std::vector<ModInt<mod>> multiply(std::vector<ModInt<mod>> a, std::vector<ModInt<mod>> b) const { if (a.empty() || b.empty()) return std::vector<ModInt<mod>>(); std::size_t siz = 1, ex = 0, s = a.size() + b.size(); while (siz < s) { siz <<= 1; ++ex; } a.resize(siz, ModInt<mod>()); b.resize(siz, ModInt<mod>()); dft(a); dft(b); for (std::size_t i = 0; i < siz; ++i) a[i] *= b[i]; idft(a); a.resize(s - 1); return a; } }; template <unsigned mod> class NTTMul { static constexpr NumberTheoreticTransform<mod> ntt = NumberTheoreticTransform<mod>(); public: static constexpr bool has_dft = true; static void dft(std::vector<ModInt<mod>> &a) { ntt.dft(a); } static void idft(std::vector<ModInt<mod>> &a) { ntt.idft(a); } static std::vector<ModInt<mod>> mul(std::vector<ModInt<mod>> lhs, std::vector<ModInt<mod>> rhs) { return ntt.multiply(std::move(lhs), std::move(rhs)); } }; } // namespace math #endif // ----- "number_theoretic_transform.hpp" ----- // ----- "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" ----- int main() { // set up io std::ios::sync_with_stdio(false); std::cin.tie(nullptr); using namespace math; constexpr unsigned mod = 998244353; using Mint = ModInt<mod>; using Poly = Polynomial<Mint, NTTMul<mod>>; std::size_t n, m; std::cin >> n >> m; Poly f(n); for (std::size_t i = 0; i < n; ++i) { std::cin >> f[i]; } std::vector<Mint> xs(m); for (std::size_t i = 0; i < m; ++i) { std::cin >> xs[i]; } std::vector<Mint> res = multipoint_evaluation(std::move(f), xs); for (std::size_t i = 0; i < m; ++i) { std::cout << res[i]; if (i + 1 == m) { std::cout << '\n'; } else { std::cout << ' '; } } }