Submit Info #53191

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp-acl suisen AC 159 ms 20.70 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.71 MiB
example_01 AC 2 ms 0.68 MiB
fft_killer_00 AC 159 ms 20.67 MiB
fft_killer_01 AC 155 ms 20.67 MiB
max_random_00 AC 156 ms 20.70 MiB
max_random_01 AC 155 ms 20.67 MiB
medium_00 AC 1 ms 0.46 MiB
medium_01 AC 2 ms 0.96 MiB
medium_02 AC 2 ms 0.89 MiB
medium_all_zero_00 AC 0 ms 0.73 MiB
medium_c_zero_00 AC 4 ms 0.76 MiB
random_00 AC 135 ms 17.58 MiB
random_01 AC 146 ms 19.27 MiB
random_02 AC 16 ms 2.92 MiB
small_00 AC 1 ms 0.68 MiB
small_01 AC 0 ms 0.68 MiB
small_02 AC 2 ms 0.68 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 1 ms 0.68 MiB
small_05 AC 1 ms 0.68 MiB
small_06 AC 1 ms 0.67 MiB
small_07 AC 3 ms 0.68 MiB
small_08 AC 2 ms 0.68 MiB
small_09 AC 1 ms 0.68 MiB
small_10 AC 1 ms 0.64 MiB
small_11 AC 1 ms 0.61 MiB
small_12 AC 2 ms 0.68 MiB
small_13 AC 0 ms 0.71 MiB
small_14 AC 3 ms 0.66 MiB
small_15 AC 1 ms 0.61 MiB

#include <atcoder/convolution> #include <atcoder/modint> #include <cassert> #include <iostream> #include <vector> #ifndef SUISEN_POLYNOMIAL_TAYLOR_SHIFT #define SUISEN_POLYNOMIAL_TAYLOR_SHIFT #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> class FPS : public std::vector<mint> { public: using std::vector<mint>::vector; FPS(const std::initializer_list<mint> l) : std::vector<mint>::vector(l) {} inline FPS& operator=(const std::vector<mint> &&f) & noexcept { std::vector<mint>::operator=(std::move(f)); return *this; } inline 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); } inline int size() const noexcept { return std::vector<mint>::size(); } inline int deg() const noexcept { return int(this->size()) - 1; } inline void cut(int max_deg) noexcept { if (deg() > max_deg) this->resize(std::max(0, max_deg + 1)); } inline int normalize() { while (this->size() and this->back() == 0) this->pop_back(); return deg(); } inline FPS pre(int max_deg) const noexcept { return FPS(this->begin(), this->begin() + std::min(this->deg(), std::max(0, max_deg)) + 1); } inline FPS operator+() const { return FPS(*this); } FPS operator-() const { FPS f(*this); for (auto &e : f) e = mint::mod() - 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; } inline FPS& operator*=(const FPS &g) { (*this) = atcoder::convolution(std::move(*this), g); return *this; } inline FPS& operator*=(FPS &&g) { (*this) = atcoder::convolution(std::move(*this), std::move(g)); return *this; } inline FPS& operator*=(const mint x) { for (auto &e : *this) e *= x; return *this; } FPS& operator/=(FPS &&g) { int fd = normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) { this->clear(); return *this; } if (gd == 0) return (*this) *= g.unsafe_get(0).inv(); static constexpr int THRESHOLD_NAIVE_POLY_DIV = 256; if (gd <= THRESHOLD_NAIVE_POLY_DIV) { (*this) = std::move(naive_quotient_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; } inline FPS& operator/=(const FPS &g) { return *this /= FPS(g); } FPS& operator%=(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_quotient_inplace(std::move(g), gd).second; (*this) -= g *= (*this / g); this->cut(gd - 1); return *this; } inline FPS& operator%=(const FPS &g) { return *this %= FPS(g); } FPS& operator<<=(const int shamt) { this->insert(this->begin(), shamt, 0); return *this; } FPS& operator>>=(const int shamt) { if (shamt > size()) this->clear(); else this->erase(this->begin(), this->begin() + shamt); return *this; } inline FPS operator+(FPS &&g) const { return FPS(*this) += std::move(g); } inline FPS operator-(FPS &&g) const { return FPS(*this) -= std::move(g); } inline FPS operator*(FPS &&g) const { return FPS(*this) *= std::move(g); } inline FPS operator/(FPS &&g) const { return FPS(*this) /= std::move(g); } inline FPS operator%(FPS &&g) const { return FPS(*this) %= std::move(g); } inline FPS operator+(const FPS &g) const { return FPS(*this) += g; } inline FPS operator-(const FPS &g) const { return FPS(*this) -= g; } inline FPS operator*(const FPS &g) const { return FPS(*this) *= g; } inline FPS operator*(const mint x) const { return FPS(*this) *= x; } inline FPS operator/(const FPS &g) const { return FPS(*this) /= g; } inline FPS operator%(const FPS &g) const { return FPS(*this) %= g; } inline friend FPS operator*(const mint x, const FPS &f) { return f * x; } inline friend FPS operator*(const mint x, FPS &&f) { return f *= x; } inline FPS operator<<(const int shamt) { return FPS(*this) <<= shamt; } inline FPS operator>>(const int shamt) { return FPS(*this) >>= shamt; } FPS& diff_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& intg_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& inv_inplace(const int max_deg) { FPS res { unsafe_get(0).inv() }; for (int k = 1; k <= max_deg;) { k *= 2; int d = 0; for (const auto &e : this->pre(k) * (res * res)) { res[d] = res[d] + res[d] - e; if (++d > k) break; } } res.cut(max_deg); (*this) = std::move(res); return *this; } FPS& log_inplace(const int max_deg) { FPS g = (2 * max_deg <= deg() ? this->diff() : this->pre(max_deg + 1).diff_inplace()); g *= this->inv_inplace(max_deg); g.cut(max_deg - 1); (*this) = std::move(g); return this->intg_inplace(); } 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& 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; } inline FPS diff() const { return FPS(*this).diff_inplace(); } inline FPS intg() const { return FPS(*this).intg_inplace(); } inline FPS inv(const int max_deg) const { return FPS(*this).inv_inplace(max_deg); } inline FPS log(const int max_deg) const { return FPS(*this).log_inplace(max_deg); } inline FPS exp(const int max_deg) const { return FPS(*this).exp_inplace(max_deg); } inline FPS pow(const long long k, const int max_deg) const { return FPS(*this).pow_inplace(k, max_deg); } private: static inv_mods<mint> invs; inline 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_quotient_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}; } }; } // namespace suisen #endif #ifndef SUISEN_FACTORIAL #define SUISEN_FACTORIAL namespace suisen { template <typename T, typename U = T> class factorial { public: factorial() {} factorial(int n) { ensure(n); } inline const T& fac(const int i) { ensure(i); return _fac[i]; } inline const U& fac_inv(const int i) { ensure(i); return _fac_inv[i]; } inline U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } inline U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector<T> _fac; static std::vector<U> _fac_inv; static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } }; template <typename T, typename U> std::vector<T> factorial<T, U>::_fac {1}; template <typename T, typename U> std::vector<U> factorial<T, U>::_fac_inv {1}; } // namespace suisen #endif namespace suisen { // return f(x + c) template <typename mint> FPS<mint> translate(const FPS<mint> &f, const mint c) { int d = f.deg(); if (d < 0) return FPS<mint> {0}; factorial<mint> fac(d); FPS<mint> expc(d + 1), g(d + 1); mint p = 1; for (int i = 0; i <= d; ++i, p *= c) { expc[i] = p * fac.fac_inv(i); g[d - i] = f[i] * fac.fac(i); } g *= expc, g.resize(d + 1); for (int i = 0; i <= d; ++i) g[i] *= fac.fac_inv(d - i); std::reverse(g.begin(), g.end()); return g; } } // namespace suisen #endif 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; mint c; std::cin >> n >> c; suisen::FPS<mint> f(n); for (mint &e : f) std::cin >> e; suisen::FPS<mint> g(suisen::translate(f, c)); for (int i = 0; i < n; ++i) { std::cout << g[i].val() << " \n"[i == n - 1]; } return 0; }