Submit Info #53620

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.37 MiB
fft_killer_00 AC 253 ms 20.33 MiB
fft_killer_01 AC 252 ms 20.70 MiB
max_random_00 AC 250 ms 20.72 MiB
max_random_01 AC 251 ms 20.71 MiB
medium_00 AC 1 ms 0.71 MiB
medium_01 AC 3 ms 0.96 MiB
medium_02 AC 3 ms 0.96 MiB
medium_all_zero_00 AC 1 ms 0.71 MiB
medium_c_zero_00 AC 1 ms 0.71 MiB
random_00 AC 210 ms 17.59 MiB
random_01 AC 229 ms 19.32 MiB
random_02 AC 27 ms 2.89 MiB
small_00 AC 1 ms 0.61 MiB
small_01 AC 1 ms 0.61 MiB
small_02 AC 1 ms 0.61 MiB
small_03 AC 1 ms 0.61 MiB
small_04 AC 1 ms 0.60 MiB
small_05 AC 1 ms 0.60 MiB
small_06 AC 1 ms 0.61 MiB
small_07 AC 1 ms 0.62 MiB
small_08 AC 1 ms 0.61 MiB
small_09 AC 1 ms 0.61 MiB
small_10 AC 1 ms 0.60 MiB
small_11 AC 1 ms 0.62 MiB
small_12 AC 1 ms 0.61 MiB
small_13 AC 1 ms 0.61 MiB
small_14 AC 1 ms 0.70 MiB
small_15 AC 1 ms 0.37 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/polynomial_taylor_shift" #include <iostream> #include <vector> #include <atcoder/modint> #include <atcoder/convolution> #include <algorithm> #include <cassert> #include <iostream> #include <vector> 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{}; } namespace suisen { template <typename mint> using convolution_t = std::vector<mint> (*)(const std::vector<mint> &, const std::vector<mint> &); 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) {} static void set_multiplication(convolution_t<mint> multiplication) { FPS<mint>::mult = multiplication; } 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 size() - 1; } inline int normalize() { while (this->size() and this->back() == 0) this->pop_back(); return deg(); } inline FPS& pre_inplace(int max_deg) noexcept { if (deg() > max_deg) this->resize(std::max(0, max_deg + 1)); return *this; } inline FPS pre(int max_deg) const noexcept { return FPS(*this).pre_inplace(max_deg); } inline FPS operator+() const { return FPS(*this); } FPS operator-() const { FPS f(*this); for (auto &e : f) e = mint::mod() - e; return f; } inline FPS& operator++() { ++(*this)[0]; return *this; } inline FPS& operator--() { --(*this)[0]; return *this; } inline FPS& operator+=(const mint x) { (*this)[0] += x; return *this; } inline FPS& operator-=(const mint x) { (*this)[0] -= x; 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-=(const 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) { return *this = FPS<mint>::mult(*this, g); } inline FPS& operator*=( FPS &&g) { return *this = FPS<mint>::mult(*this, g); } inline FPS& operator*=(const mint x) { for (auto &e : *this) e *= x; return *this; } FPS& operator/=(FPS &&g) { const 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_QUOTIENT = 256; if (gd <= THRESHOLD_NAIVE_POLY_QUOTIENT) { *this = std::move(naive_div_inplace(std::move(g), gd).first); return *this; } std::reverse(this->begin(), this->end()), std::reverse(g.begin(), g.end()); const int k = fd - gd; *this *= g.inv_inplace(k), this->resize(k + 1); std::reverse(this->begin(), this->end()); return *this; } 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_REMAINDER = 256; if (gd <= THRESHOLD_NAIVE_REMAINDER) return naive_div_inplace(std::move(g), gd).second; *this -= g * (*this / g); return pre_inplace(gd - 1); } inline FPS& operator/=(const FPS &g) { return *this /= FPS(g); } 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 mint x) const { return FPS(*this) += x; } 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 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) { FPS tmp(this->pre(k * 2) * (res * res)); res *= 2, res -= tmp.pre_inplace(2 * k); } return *this = std::move(res), pre_inplace(max_deg); } FPS& log_inplace(const int max_deg) { FPS f_inv = inv(max_deg); diff_inplace(), *this *= f_inv, pre_inplace(max_deg - 1), intg_inplace(); return *this; } FPS& exp_inplace(const int max_deg) { FPS res {1}; for (int k = 1; k <= max_deg; k *= 2) res *= ++(pre(k * 2) - res.log(k * 2)), res.pre_inplace(k * 2); return *this = std::move(res), pre_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), *this *= k, exp_inplace(max_deg), *this *= base.pow(k); return *this <<= tlz * k, pre_inplace(max_deg); } 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; static convolution_t<mint> mult; 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_div_inplace(FPS &&g, const int gd) { const 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); } return {q, pre_inplace(gd - 1)}; } }; template <typename mint> convolution_t<mint> FPS<mint>::mult = [](const auto &, const auto &) { std::cerr << "convolution function is not available." << std::endl; assert(false); return std::vector<mint>{}; }; } // namespace suisen #include <cassert> #include <vector> 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 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 using mint = atcoder::modint998244353; int main() { suisen::FPS<mint>::set_multiplication([](const auto &a, const auto &b) { return atcoder::convolution(a, b); }); int n, c; std::cin >> n >> c; suisen::FPS<mint> f(n); for (int i = 0; i < n; ++i) { int coef; std::cin >> coef; f[i] = coef; } auto g = suisen::translate(f, mint(c)); for (int i = 0; i < n; ++i) { std::cout << g[i].val() << " \n"[i == n - 1]; } return 0; }