Submit Info #38294

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp kya AC 273 ms 18.73 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 2 ms 0.57 MiB
fft_killer_00 AC 273 ms 18.65 MiB
fft_killer_01 AC 272 ms 18.73 MiB
max_random_00 AC 269 ms 18.73 MiB
max_random_01 AC 270 ms 18.67 MiB
medium_00 AC 2 ms 0.67 MiB
medium_01 AC 4 ms 0.92 MiB
medium_02 AC 4 ms 0.91 MiB
medium_all_zero_00 AC 3 ms 0.67 MiB
medium_c_zero_00 AC 2 ms 0.70 MiB
random_00 AC 231 ms 16.57 MiB
random_01 AC 254 ms 17.75 MiB
random_02 AC 32 ms 2.76 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 1 ms 0.56 MiB
small_02 AC 3 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 0 ms 0.61 MiB
small_06 AC 1 ms 0.66 MiB
small_07 AC 1 ms 0.61 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 0 ms 0.61 MiB
small_10 AC 0 ms 0.67 MiB
small_11 AC 1 ms 0.67 MiB
small_12 AC 2 ms 0.67 MiB
small_13 AC 1 ms 0.66 MiB
small_14 AC 1 ms 0.65 MiB
small_15 AC 2 ms 0.62 MiB

/* "modint.cpp" */ #include <iostream> #include <cstdint> #include <cassert> template<int Modulus> struct modint { using value_type = int; static constexpr value_type mod = Modulus; static_assert(mod > 1, "Modulus must be greater than 1"); static constexpr value_type get_mod () { return mod; } private : value_type x; friend constexpr value_type get_value (const modint<Modulus> &p) noexcept { return p.x; } template<class T> static constexpr value_type normalize (T value) noexcept { if (value < 0) { value = (-value) % mod; return (value ? mod - value : value); } return (value % mod); } public : constexpr modint () noexcept : x(0) { } template<class T> constexpr modint (T value) noexcept : x(normalize(value)) { } constexpr modint operator+ () const noexcept { return modint(*this); } constexpr modint operator- () noexcept { return modint(x ? mod - x : x); } constexpr modint &operator++ () noexcept { if (++x == mod) x = 0; return (*this); } constexpr modint &operator-- () noexcept { if (x == 0) x = mod; --x; return (*this); } constexpr modint operator++ (int) noexcept { modint res = (*this); ++*this; return res; } constexpr modint operator-- (int) noexcept { modint res = (*this); --*this; return res; } constexpr modint &operator+= (const modint &p) noexcept { if ((x += p.x) >= mod) x -= mod; return (*this); } constexpr modint &operator-= (const modint &p) noexcept { if ((x += mod - p.x) >= mod) x -= mod; return (*this); } constexpr modint &operator*= (const modint &p) noexcept { x = (int)(1LL * x * p.x % mod); return (*this); } constexpr modint &operator/= (const modint &p) noexcept { return ((*this) *= inverse(p)); } constexpr modint operator+ (const modint &p) const noexcept { return (modint(*this) += p); } constexpr modint operator- (const modint &p) const noexcept { return (modint(*this) -= p); } constexpr modint operator* (const modint &p) const noexcept { return (modint(*this) *= p); } constexpr modint operator/ (const modint &p) const noexcept { return (modint(*this) /= p); } constexpr bool operator== (const modint &p) const noexcept { return (x == p.x); } constexpr bool operator!= (const modint &p) const noexcept { return (x != p.x); } friend constexpr std::ostream &operator<< (std::ostream &os, const modint<Modulus> &p) noexcept { return (os << p.x); } friend constexpr std::istream &operator>> (std::istream &is, modint<Modulus> &p) noexcept { long long v; is >> v; p = modint<Modulus>(v); return (is); } friend constexpr modint<Modulus> inverse (const modint<Modulus> &value) noexcept { return pow(value, mod - 2); } friend constexpr modint<Modulus> pow (modint<Modulus> value, std::uint_fast64_t idx) noexcept { modint<Modulus> ret = 1; while (idx > 0) { if (idx & 1) ret *= value; value *= value; idx >>= 1; } return ret; } }; /* "number_theoretic_transform.cpp" */ #include <vector> namespace number_theoretic_transform { // Compile time primitive root constexpr int constexpr_primitive_root (int m) noexcept { if (m == 998244353) return 3; // 2^23 * 119 + 1 if (m == 469762049) return 3; // 2^26 * 7 + 1 if (m == 167772161) return 3; // 2^25 * 5 + 1 if (m == 754974721) return 11; // 2^24 * 3^2 * 5^2 + 1 if (m == 1224736769) return 3; // 2^24 * 73 + 1 if (m == 377487361) return 7; // 2^23 * 3^2 * 5 + 1 if (m == 595591169) return 3; // 2^23 * 71 + 1 if (m == 645922817) return 3; // 2^23 * 7 * 11 + 1 if (m == 880803841) return 26; // 2^23 * 3 * 5 * 7 + 1 if (m == 897581057) return 3; // 2^23 * 107 + 1 if (m == 104857601) return 3; // 2^22 * 5^2 + 1 if (m == 113246209) return 7; // 2^22 * 3^3 + 1 if (m == 138412033) return 5; // 2^22 * 3 * 11 + 1 if (m == 155189249) return 6; // 2^22 * 37 + 1 if (m == 163577857) return 23; // 2^22 * 3 * 13 + 1 if (m == 230686721) return 6; // 2^22 * 5 * 11 + 1 if (m == 415236097) return 5; // 2^22 * 3^2 * 11 + 1 if (m == 666894337) return 5; // 2^22 * 3 * 53 + 1 if (m == 683671553) return 3; // 2^22 * 163 + 1 if (m == 918552577) return 5; // 2^22 * 3 * 73 + 1 if (m == 935329793) return 3; // 2^22 * 223 + 1 if (m == 943718401) return 7; // 2^22 * 3^2 * 5^2 + 1 if (m == 985661441) return 3; // 2^22 * 5 * 47 + 1 if (m == 111149057) return 3; // 2^21 * 53 + 1 if (m == 132120577) return 5; // 2^21 * 3^2 * 7 + 1 if (m == 136314881) return 3; // 2^21 * 5 * 13 + 1 if (m == 169869313) return 5; // 2^21 * 3^4 + 1 if (m == 186646529) return 3; // 2^21 * 89 + 1 if (m == 199229441) return 3; // 2^21 * 5 * 19 + 1 if (m == 211812353) return 3; // 2^21 * 101 + 1 if (m == 249561089) return 3; // 2^21 * 7 * 17 + 1 if (m == 257949697) return 5; // 2^21 * 3 * 41 + 1 if (m == 270532609) return 22; // 2^21 * 3 * 43 + 1 if (m == 274726913) return 3; // 2^21 * 131 + 1 if (m == 383778817) return 5; // 2^21 * 3 * 61 + 1 if (m == 387973121) return 6; // 2^21 * 5 * 37 + 1 if (m == 459276289) return 11; // 2^21 * 3 * 73 + 1 if (m == 463470593) return 3; // 2^21 * 13 * 17 + 1 if (m == 576716801) return 6; // 2^21 * 5^2 * 11 + 1 if (m == 597688321) return 11; // 2^21 * 3 * 5 * 19 + 1 if (m == 635437057) return 11; // 2^21 * 3 * 101 + 1 if (m == 639631361) return 6; // 2^21 * 5 * 61 + 1 if (m == 648019969) return 17; // 2^21 * 3 * 103 + 1 if (m == 710934529) return 17; // 2^21 * 3 * 113 + 1 if (m == 715128833) return 3; // 2^21 * 11 * 31 + 1 if (m == 740294657) return 3; // 2^21 * 353 + 1 if (m == 786432001) return 7; // 2^21 * 3 * 5^3 + 1 if (m == 799014913) return 13; // 2^21 * 3 * 127 + 1 if (m == 824180737) return 5; // 2^21 * 3 * 131 + 1 if (m == 899678209) return 7; // 2^21 * 3 * 11 * 13 + 1 if (m == 924844033) return 5; // 2^21 * 3^2 * 7^2 + 1 if (m == 950009857) return 7; // 2^21 * 3 * 151 + 1 if (m == 962592769) return 7; // 2^21 * 3^3 * 17 + 1 if (m == 975175681) return 17; // 2^21 * 3 * 5 * 31 + 1 if (m == 1004535809) return 3; // 2^21 * 479 + 1 if (m == 1012924417) return 5; // 2^21 * 3 * 7 * 23 + 1 return -1; } constexpr int constexpr_countr_zero (int x) noexcept { return __builtin_ctz(x); } template<int m> constexpr int primitive_root = constexpr_primitive_root(m); template<int m> constexpr int countr_zero = constexpr_countr_zero(m); template<int mod> constexpr bool ntt_friendly (size_t sz) noexcept { constexpr int b = countr_zero<mod - 1>; return size_t(1 << b) > sz; } template<class mint> inline std::vector<mint> zeta_pow (size_t n, const mint &zeta) noexcept { std::vector<mint> zetas((n >> 1), 1); for (size_t i = 0; i + 1 < size(zetas); i++) { zetas[i + 1] = zetas[i] * zeta; } return zetas; } template<int mod, int g, class mint> void ntt (std::vector<mint> &f) noexcept { const size_t n = size(f); for (size_t m = n; m > 1; m >>= 1) { const auto zetas = zeta_pow(m, pow(mint(g), (mod - 1) / m)); for (size_t s = 0; s < n; s += m) { for (size_t i = 0, j = s; i < (m >> 1); ++i, ++j) { const mint lhs = f[j]; const mint rhs = f[j + (m >> 1)]; f[j] = lhs + rhs; f[j + (m >> 1)] = (lhs - rhs) * zetas[i]; } } } } template<int mod, int g, class mint> void inverse_ntt (std::vector<mint> &f) noexcept { const size_t n = size(f); for (size_t m = 2; m <= n; m <<= 1) { const auto zetas = zeta_pow(m, pow(mint(g), (mod - 1) - (mod - 1) / m)); for (size_t s = 0; s < n; s += m) { for (size_t i = 0, j = s; i < (m >> 1); ++i, ++j) { const mint lhs = f[j]; const mint rhs = f[j + (m >> 1)] * zetas[i]; f[j] = lhs + rhs; f[j + (m >> 1)] = lhs - rhs; } } } } template<class mint> std::vector<mint> normal_convolution (std::vector<mint> f, std::vector<mint> g) noexcept { if (f.empty() or g.empty()) return {}; if (std::min(size(f), size(g)) <= 60) { size_t n = size(f), m = size(g); if (n < m) { std::swap(n, m); std::swap(f, g); } std::vector<mint> ans(n + m - 1, 0); for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < m; j++) { ans[i + j] += f[i] * g[j]; } } return ans; } size_t n = 1; static constexpr int mod = mint::mod; static constexpr int root = primitive_root<mod>; const size_t default_size = size(f) + size(g) - 1; while (n < default_size) n <<= 1; f.resize(n, 0); g.resize(n, 0); ntt<mod, root>(f); ntt<mod, root>(g); for (size_t i = 0; i < n; i++) f[i] *= g[i]; inverse_ntt<mod, root>(f); f.resize(default_size); const mint inv_n = inverse(mint(n)); for (auto &f_i : f) f_i *= inv_n; return f; } template<int MOD, class Tp> inline std::vector<modint<MOD>> sub_multiply (const std::vector<Tp> &f, const std::vector<Tp> &g) noexcept { std::vector<modint<MOD>> a(size(f)), b(size(g)); for (size_t i = 0; i < size(f); i++) a[i] = modint<MOD>(get_value(f[i])); for (size_t i = 0; i < size(g); i++) b[i] = modint<MOD>(get_value(g[i])); return normal_convolution(a, b); } // 乗算後の値が 59501818244292734739283969 (> (10^9 + 7)^2 * 5 * 10^7) まで対応 template<class mint> std::vector<mint> any_mod_convolution (const std::vector<mint> &f, const std::vector<mint> &g) noexcept { if (std::min(size(f), size(g)) <= 60) return sub_multiply<mint::get_mod()>(f, g); static constexpr int MOD0 = 167772161; // 2^25 * 5 + 1 static constexpr int MOD1 = 469762049; // 2^26 * 7 + 1 static constexpr int MOD2 = 754974721; // 2^24 * 45 + 1 static constexpr mint M0 = 167772161; // MOD0 (mod MOD) static constexpr mint M0M1 = 564826938; // MOD0 * MOD1 (mod MOD) static constexpr modint<MOD1> I0 = 104391568; // MOD0^-1 (mod MOD1) static constexpr modint<MOD2> I1 = 399692502; // MOD1^-1 (mod MOD2) static constexpr modint<MOD2> I0I1 = 190329765; // (MOD0 * MOD1)^-1 (mod MOD2) const auto r0 = sub_multiply<MOD0>(f, g); const auto r1 = sub_multiply<MOD1>(f, g); const auto r2 = sub_multiply<MOD2>(f, g); std::vector<mint> h(size(r0)); for (size_t i = 0; i < size(h); i++) { const int x0 = get_value(r0[i]); const int x1 = get_value(I0 * (r1[i] - x0)); const int x2 = get_value(I0I1 * (r2[i] - x0) - I1 * x1); h[i] = M0M1 * x2 + M0 * x1 + x0; } return h; } template<class mint> std::vector<mint> convolution (const std::vector<mint> &f, const std::vector<mint> &g) noexcept { if (f.empty() or g.empty()) return std::vector<mint>(); if (ntt_friendly<mint::get_mod()>(size(f) + size(g) - 1)) { return normal_convolution(f, g); } else { return any_mod_convolution(f, g); } } } // namespace number_theoretic_transform #include <vector> #include <cassert> #include <algorithm> template<class Tp> struct formal_power_series : private std::vector<Tp> { using Self = formal_power_series<Tp>; using Base = std::vector<Tp>; using reference = typename Base::reference; using const_reference = typename Base::const_reference; using size_type = typename Base::size_type; using value_type = typename Base::value_type; using Base::vector; using Base::operator=; using Base::begin; using Base::end; using Base::rbegin; using Base::rend; using Base::size; using Base::resize; using Base::empty; using Base::reserve; using Base::operator[]; using Base::at; using Base::front; using Base::back; using Base::assign; using Base::push_back; using Base::emplace_back; using Base::pop_back; using Base::swap; using Base::clear; void normalize () noexcept { while (not empty() and back() == Tp(0)) pop_back(); } constexpr Self prev (size_type deg) const noexcept { return Self(std::begin(*this), std::begin(*this) + std::min(size(), deg)); } constexpr Self operator+ () const noexcept { return Self(*this); } constexpr Self operator- () noexcept { Self res(*this); for (auto& e : res) e = -e; return res; } constexpr Self &operator+= (const Self &fps) noexcept { if (size() < fps.size()) resize(fps.size(), 0); for (size_type i = 0; i < fps.size(); i++) at(i) += fps.at(i); return (*this); } constexpr Self &operator-= (const Self &fps) noexcept { if (size() < fps.size()) resize(fps.size(), 0); for (size_type i = 0; i < fps.size(); i++) at(i) -= fps.at(i); return (*this); } constexpr Self &operator*= (const Self &fps) noexcept { (*this) = number_theoretic_transform::convolution((*this), fps); return (*this); } constexpr Self &operator/= (const Self &fps) noexcept { return (*this) *= inverse(fps); } constexpr Self &operator%= (const Self &fps) noexcept { (*this) -= (*this) / fps * fps; return (*this); } constexpr Self &operator+= (const_reference x) noexcept { if (empty()) resize(1); at(0) += x; return (*this); } constexpr Self &operator-= (const_reference x) noexcept { if (empty()) resize(1); at(0) -= x; return (*this); } constexpr Self &operator*= (const_reference x) noexcept { for (size_type i = 0; i < size(); i++) at(i) *= x; return (*this); } constexpr Self &operator/= (const_reference x) noexcept { for (size_type i = 0; i < size(); i++) at(i) /= x; return (*this); } constexpr Self operator+ (const Self &fps) const noexcept { return Self(*this) += fps; } constexpr Self operator- (const Self &fps) const noexcept { return Self(*this) -= fps; } constexpr Self operator* (const Self &fps) const noexcept { return Self(*this) *= fps; } constexpr Self operator/ (const Self &fps) const noexcept { return Self(*this) /= fps; } constexpr Self operator% (const Self &fps) const noexcept { return Self(*this) %= fps; } constexpr Self operator+ (const_reference x) const noexcept { return Self(*this) += x; } constexpr Self operator- (const_reference x) const noexcept { return Self(*this) -= x; } constexpr Self operator* (const_reference x) const noexcept { return Self(*this) *= x; } constexpr Self operator/ (const_reference x) const noexcept { return Self(*this) /= x; } friend constexpr value_type evaluate (const Self &fps, const_reference x) noexcept { value_type res = value_type(0); for (size_type i = fps.size(); i > 0; i--) { res = res * x + fps[i - 1]; } return res; } friend Self inverse (const Self &fps, size_type deg) noexcept { assert(not fps.empty() and not (fps[0] == 0)); if (deg == 0) return {}; Self res{inverse(fps[0])}; for (size_type n = 2; res.size() < deg; n <<= 1) { auto g = res * fps.prev(n); g.resize(n); g[0] -= value_type(2); res *= -g; res.resize(n); } return res.resize(deg), res; } friend Self inverse (const Self &fps) noexcept { return inverse(fps, fps.size()); } friend Self differential (const Self &fps) noexcept { if (fps.empty()) return {}; const size_type n = fps.size(); Self res(n - 1); for (size_type i = 0; i + 1 < n; i++) { res[i] = fps[i + 1] * value_type(i + 1); } return res; } friend Self integral (const Self &fps) noexcept { const size_type n = fps.size(); Self res(n + 1, 0); for (size_type i = 0; i < n; i++) { res[i + 1] = fps[i] / value_type(i + 1); } return res; } friend Self log (const Self &fps, size_type deg) noexcept { assert(not fps.empty() and fps[0] == value_type(1)); if (deg == 0) return {}; auto res = differential(fps) * inverse(fps, deg); res.resize(deg - 1); return integral(res); } friend Self log (const Self &fps) noexcept { return log(fps, fps.size()); } friend Self exp (const Self &fps, size_type deg) noexcept { assert(not fps.empty() and fps[0] == value_type(0)); if (deg == 0) return {}; Self res{value_type(1)}; for (size_type n = 2; res.size() < deg; n <<= 1) { res = res * (fps.prev(n) - log(res, n) + value_type(1)); res.resize(n); } return res.resize(deg), res; } friend Self exp (const Self &fps) noexcept { return exp(fps, fps.size()); } friend Self pow (Self fps, std::uint_fast64_t idx, size_type deg) noexcept { Self res{value_type(1)}; while (idx > 0) { if (idx & 1) { res *= fps; res.resize(deg); } fps *= fps; fps.resize(deg); idx >>= 1; } return res; } friend Self pow (const Self &fps, std::uint_fast64_t idx) noexcept { return pow(fps, idx, fps.size()); } friend Self taylor_shift (Self fps, const_reference c) noexcept { const size_type n = fps.size(); value_type fact = 1; std::vector<value_type> ifact(n + 1); for (size_type i = 0; i < n; i++) { fps[i] *= fact; fact *= (i + 1); } ifact[n] = inverse(fact); for (size_type i = n; i > 0; i--) ifact[i - 1] = ifact[i] * i; std::reverse(fps.begin(), fps.end()); Self g(n); value_type cp = 1; for (size_type i = 0; i < n; i++) { g[i] = cp * ifact[i]; cp *= c; } fps *= g; fps.resize(n); std::reverse(fps.begin(), fps.end()); for (size_type i = 0; i < n; i++) fps[i] *= ifact[i]; return fps; } }; #include <iostream> #include <queue> constexpr int MOD = 998244353; using mint = modint<MOD>; int main() { size_t n; mint c; std::cin >> n >> c; formal_power_series<mint> f(n); for (auto &e : f) std::cin >> e; for (const auto &b : taylor_shift(f, c)) { std::cout << b << ' '; } std::cout << std::endl; return 0; }