Submit Info #53169

Problem Lang User Status Time Memory
Polynomial Interpolation cpp-acl suisen AC 1444 ms 47.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 2 ms 0.68 MiB
max_random_00 AC 1444 ms 47.24 MiB
max_random_01 AC 1442 ms 47.30 MiB
random_00 AC 1387 ms 46.77 MiB
random_01 AC 783 ms 36.96 MiB
random_02 AC 526 ms 21.28 MiB

#include <atcoder/convolution> #include <atcoder/modint> #include <cassert> #include <iostream> #include <vector> #ifndef SUISEN_FPS #define SUISEN_FPS #ifndef SUISEN_INV_MOD #define SUISEN_INV_MOD namespace suisen { template <typename mint> class inv_mods { public: inv_mods() {} inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = {0, 1}, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; } #endif namespace suisen { template <typename mint> struct FPS : public std::vector<mint> { using std::vector<mint>::vector; FPS(const std::initializer_list<mint> l) : std::vector<mint>::vector(l) {} FPS& operator=(const std::vector<mint> &&f) & noexcept { std::vector<mint>::operator=(std::move(f)); return *this; } FPS& operator=(const std::vector<mint> &f) & { std::vector<mint>::operator=(f); return *this; } inline const mint operator[](int n) const noexcept { return n <= deg() ? unsafe_get(n) : 0; } inline mint& operator[](int n) noexcept { ensure_deg(n); return unsafe_get(n); } int deg() const noexcept { return int(this->size()) - 1; } void cut(int max_deg) noexcept { if (deg() > max_deg) this->resize(std::max(0, max_deg + 1)); } FPS pre(int max_deg) const noexcept { if (max_deg < 0) return { 0 }; return FPS(this->begin(), this->begin() + std::min(this->deg(), max_deg) + 1); } FPS operator-() const { FPS f(*this); for (auto &e : f) e = -e; return f; } FPS& operator+=(const FPS &g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i); return *this; } FPS& operator+=(FPS &&g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i); return *this; } FPS& operator-=(const FPS &g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i); return *this; } FPS& operator-=(FPS &&g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i); return *this; } FPS& operator*=(const FPS &g) { (*this) = atcoder::convolution(std::move(*this), g); return *this; } FPS& operator*=(FPS &&g) { (*this) = atcoder::convolution(std::move(*this), std::move(g)); return *this; } FPS& operator*=(const mint x) { for (auto &e : *this) e *= x; return *this; } FPS operator+(FPS &&g) const { return g += *this; } FPS operator-(FPS &&g) const { g.ensure_deg(deg()); for (int i = 0; i <= deg(); ++i) g.unsafe_get(i) = unsafe_get(i) - g.unsafe_get(i); return g; } FPS operator*(FPS &&g) const { return g *= *this; } FPS operator+(const FPS &g) const { return FPS(*this) += g; } FPS operator-(const FPS &g) const { return FPS(*this) -= g; } FPS operator*(const FPS &g) const { return FPS(*this) *= g; } FPS operator*(const mint x) const { return FPS(*this) *= x; } friend FPS operator*(const mint x, const FPS &f) { return f * x; } friend FPS operator*(const mint x, FPS &&f) { return f *= x; } FPS& operator<<=(const int shamt) { this->insert(this->begin(), shamt, 0); return *this; } FPS& operator>>=(const int shamt) { if (shamt > int(this->size())) { this->clear(); } else { this->erase(this->begin(), this->begin() + shamt); } return *this; } FPS operator<<(const int shamt) { return FPS(*this) <<= shamt; } FPS operator>>(const int shamt) { return FPS(*this) >>= shamt; } FPS& inv_inplace(const int max_deg) { FPS res { unsafe_get(0).inv() }; for (int k = 1; k <= max_deg;) { k *= 2; int deg = 0; for (const auto &e : this->pre(k) * (res * res)) { res[deg] = res[deg] * 2 - e; if (++deg > k) break; } } res.cut(max_deg); (*this) = std::move(res); return *this; } FPS inv(const int max_deg) const { return FPS(*this).inv_inplace(max_deg); } FPS& differentiate_inplace() { if (this->size() == 0) return *this; for (int i = 1; i <= deg(); ++i) unsafe_get(i - 1) = unsafe_get(i) * i; this->pop_back(); return *this; } FPS differentiate() const { return FPS(*this).differentiate_inplace(); } FPS& integrate_inplace() { int d = deg(); ensure_deg(d + 1); for (int i = d; i >= 0; --i) { unsafe_get(i + 1) = unsafe_get(i) * invs[i + 1]; } unsafe_get(0) = 0; return *this; } FPS integrate() const { return FPS(*this).integrate_inplace(); } FPS& log_inplace(const int max_deg) { FPS g = (2 * max_deg <= deg() ? this->differentiate() : this->pre(max_deg + 1).differentiate_inplace()); g *= this->inv_inplace(max_deg); g.cut(max_deg - 1); (*this) = std::move(g); return this->integrate_inplace(); } FPS log(const int max_deg) const { return FPS(*this).log_inplace(max_deg); } FPS& exp_inplace(const int max_deg) { FPS res { 1 }; for (int k = 1; k <= max_deg;) { k *= 2; FPS tmp = this->pre(k); tmp -= res.log(k); ++tmp[0]; res *= std::move(tmp); res.cut(k); } res.cut(max_deg); (*this) = std::move(res); return *this; } FPS exp(const int max_deg) const { return FPS(*this).exp_inplace(max_deg); } FPS& pow_inplace(const long long k, const int max_deg) { int tlz = 0; while (tlz <= deg() and unsafe_get(tlz) == 0) ++tlz; if (tlz * k > max_deg) { this->clear(); return *this; } (*this) >>= tlz; mint base = (*this)[0]; ((((*this) *= base.inv()).log_inplace(max_deg) *= k).exp_inplace(max_deg) *= base.pow(k)) <<= tlz * k; this->cut(max_deg); return *this; } FPS pow(const long long k, const int max_deg) const { return FPS(*this).pow_inplace(k, max_deg); } FPS& poly_div_inplace(FPS &&g) { int fd = normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) { this->clear(); return *this; } if (gd == 0) return (*this) *= g[0].inv(); static constexpr int THRESHOLD_NAIVE_POLY_DIV = 256; if (gd <= THRESHOLD_NAIVE_POLY_DIV) { (*this) = std::move(naive_poly_div_inplace(std::move(g), gd).first); return *this; } std::reverse(this->begin(), this->end()); std::reverse(g.begin(), g.end()); int k = fd - gd; (*this) *= g.inv_inplace(k); this->resize(k + 1); std::reverse(this->begin(), this->end()); return *this; } FPS& poly_div_inplace(const FPS &g) { return poly_div_inplace(FPS(g)); } FPS poly_div( FPS &&g) const { return FPS(*this).poly_div_inplace(std::move(g)); } FPS poly_div(const FPS &g) const { return FPS(*this).poly_div_inplace(FPS(g)); } FPS& poly_mod_inplace(FPS &&g) { int fd = normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) return *this; if (gd == 0) { this->clear(); return *this; } static constexpr int THRESHOLD_NAIVE_POLY_DIV = 256; if (gd <= THRESHOLD_NAIVE_POLY_DIV) return naive_poly_div_inplace(std::move(g), gd).second; FPS q = poly_div(g); return (*this) -= std::move(g) * std::move(q); } FPS& poly_mod_inplace(const FPS &g) { return poly_mod_inplace(FPS(g)); } FPS poly_mod( FPS &&g) const { return FPS(*this).poly_mod_inplace(std::move(g)); } FPS poly_mod(const FPS &g) const { return FPS(*this).poly_mod_inplace(g); } private: static inv_mods<mint> invs; void ensure_deg(int d) { if (deg() < d) this->resize(d + 1, 0); } inline const mint& unsafe_get(int i) const { return std::vector<mint>::operator[](i); } inline mint& unsafe_get(int i) { return std::vector<mint>::operator[](i); } std::pair<FPS, FPS&> naive_poly_div_inplace(FPS &&g, const int gd) { int k = deg() - gd; mint head_inv = g.unsafe_get(gd).inv(); FPS q(k + 1); for (int i = k; i >= 0; --i) { mint div = this->unsafe_get(i + gd) * head_inv; q.unsafe_get(i) = div; for (int j = 0; j <= gd; ++j) this->unsafe_get(i + j) -= div * g.unsafe_get(j); } this->cut(gd - 1); return {q, *this}; } int normalize() { while (this->size() and this->back() == 0) this->pop_back(); return deg(); } }; } // namespace suisen #endif namespace suisen { template <typename T> T lagrange_interpolation(const std::vector<T> &ys, const T t) { const int n = ys.size(); T fac = 1; for (int i = 1; i < n; ++i) fac *= i; std::vector<T> fci(n), suf(n); fci[n - 1] = T(1) / fac; suf[n - 1] = 1; for (int i = n - 1; i > 0; --i) { fci[i - 1] = fci[i] * i; suf[i - 1] = suf[i] * (t - i); } T prf = 1, res = 0; for (int i = 0; i < n; ++i) { T val = ys[i] * prf * suf[i] * fci[i] * fci[n - i - 1]; if ((n - 1 - i) & 1) { res -= val; } else { res += val; } prf *= t - i; } return res; } template <typename mint> FPS<mint> polynomial_interpolation(const std::vector<mint> &xs, const std::vector<mint> &ys) { assert(xs.size() == ys.size()); int n = xs.size(); int k = 1; while (k < n) k <<= 1; std::vector<FPS<mint>> seg(k << 1), g(k << 1); for (int i = 0; i < n; ++i) seg[k + i] = FPS<mint> {-xs[i], 1}; for (int i = n; i < k; ++i) seg[k + i] = FPS<mint> {1}; for (int i = k - 1; i > 0; --i) seg[i] = seg[i * 2] * seg[i * 2 + 1]; g[1] = std::move(seg[1].differentiate_inplace()); for (int i = 1; i < k; ++i) { int l = 2 * i, r = l + 1; g[l] = g[i].poly_mod(seg[l]); g[r] = g[i].poly_mod(seg[r]); } for (int i = 0; i < n; ++i) g[k + i] = FPS<mint> {ys[i] / g[k + i][0]}; for (int i = n; i < k; ++i) g[k + i] = FPS<mint> {0}; for (int i = k - 1; i > 0; --i) { int l = 2 * i, r = l + 1; g[i] = std::move(g[l]); g[i] *= std::move(seg[r]); g[i] += std::move(g[r] *= seg[l]); seg[l].clear(), seg[r].clear(), g[r].clear(); } return g[1]; } } // namespace suisen using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } // ! code from here int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> x(n), y(n); for (mint &e : x) std::cin >> e; for (mint &e : y) std::cin >> e; auto f = suisen::polynomial_interpolation(x, y); f.resize(n); for (int i = 0; i < n; ++i) { std::cout << f[i] << " \n"[i == n - 1]; } return 0; }