Submit Info #33980

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp-acl pachicobue AC 153 ms 21.13 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.61 MiB
fft_killer_00 AC 153 ms 21.06 MiB
fft_killer_01 AC 151 ms 21.05 MiB
max_random_00 AC 151 ms 21.13 MiB
max_random_01 AC 152 ms 21.06 MiB
medium_00 AC 2 ms 0.73 MiB
medium_01 AC 7 ms 1.07 MiB
medium_02 AC 2 ms 1.04 MiB
medium_all_zero_00 AC 2 ms 0.80 MiB
medium_c_zero_00 AC 0 ms 0.74 MiB
random_00 AC 137 ms 18.06 MiB
random_01 AC 143 ms 19.63 MiB
random_02 AC 17 ms 3.33 MiB
small_00 AC 1 ms 0.62 MiB
small_01 AC 1 ms 0.62 MiB
small_02 AC 2 ms 0.62 MiB
small_03 AC 1 ms 0.62 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 1 ms 0.67 MiB
small_06 AC 1 ms 0.67 MiB
small_07 AC 2 ms 0.67 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 1 ms 0.68 MiB
small_10 AC 2 ms 0.62 MiB
small_11 AC 2 ms 0.63 MiB
small_12 AC 0 ms 0.61 MiB
small_13 AC 0 ms 0.62 MiB
small_14 AC 1 ms 0.67 MiB
small_15 AC 3 ms 0.67 MiB

#include <bits/stdc++.h> using ll = long long; using uint = unsigned int; using ull = unsigned long long; using ld = long double; template<typename T> using max_heap = std::priority_queue<T>; template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>; constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; } constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; } constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); } constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; } constexpr ull ceil2(const ull v) { return 1ULL << clog(v); } constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; } constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; } class range { private: struct itr { itr(const int start = 0, const int step = 1) : m_cnt{start}, m_step{step} {} bool operator!=(const itr& it) const { return m_cnt != it.m_cnt; } int& operator*() { return m_cnt; } itr& operator++() { return m_cnt += m_step, *this; } int m_cnt, m_step; }; int m_start, m_end, m_step; public: range(const int start, const int end, const int step = 1) : m_start{start}, m_end{end}, m_step{step} { assert(m_step != 0); if (m_step > 0) { m_end = m_start + std::max(m_step - 1, m_end - m_start + m_step - 1) / m_step * m_step; } if (m_step < 0) { m_end = m_start - std::max(-m_step - 1, m_start - m_end - m_step - 1) / (-m_step) * (-m_step); } } itr begin() const { return itr{m_start, m_step}; } itr end() const { return itr{m_end, m_step}; } }; range rep(const int end, const int step = 1) { return range(0, end, step); } range per(const int rend, const int step = -1) { return range(rend - 1, -1, step); } struct modinfo { const uint mod, root, max2p; }; template<const modinfo& info> class modint { public: static constexpr const uint& mod = info.mod; static constexpr const uint& root = info.root; static constexpr const uint& max2p = info.max2p; constexpr modint() : m_val{0} {} constexpr modint(const ll v) : m_val{normll(v)} {} constexpr modint(const modint& m) = default; constexpr void set_raw(const uint v) { m_val = v; } constexpr modint& operator=(const modint& m) { return m_val = m(), (*this); } constexpr modint& operator=(const ll v) { return m_val = normll(v), (*this); } constexpr modint operator+() const { return *this; } constexpr modint operator-() const { return modint{0} - (*this); } constexpr modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; } constexpr modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; } constexpr modint& operator*=(const modint& m) { return m_val = normll((ll)m_val * (ll)m() % (ll)mod), *this; } constexpr modint& operator/=(const modint& m) { return *this *= m.inv(); } constexpr modint& operator+=(const ll val) { return *this += modint{val}; } constexpr modint& operator-=(const ll val) { return *this -= modint{val}; } constexpr modint& operator*=(const ll val) { return *this *= modint{val}; } constexpr modint& operator/=(const ll val) { return *this /= modint{val}; } constexpr modint operator+(const modint& m) const { return modint{*this} += m; } constexpr modint operator-(const modint& m) const { return modint{*this} -= m; } constexpr modint operator*(const modint& m) const { return modint{*this} *= m; } constexpr modint operator/(const modint& m) const { return modint{*this} /= m; } constexpr modint operator+(const ll v) const { return *this + modint{v}; } constexpr modint operator-(const ll v) const { return *this - modint{v}; } constexpr modint operator*(const ll v) const { return *this * modint{v}; } constexpr modint operator/(const ll v) const { return *this / modint{v}; } constexpr bool operator==(const modint& m) const { return m_val == m(); } constexpr bool operator!=(const modint& m) const { return not(*this == m); } constexpr friend modint operator+(const ll v, const modint& m) { return modint{v} + m; } constexpr friend modint operator-(const ll v, const modint& m) { return modint{v} - m; } constexpr friend modint operator*(const ll v, const modint& m) { return modint{v} * m; } constexpr friend modint operator/(const ll v, const modint& m) { return modint{v} / m; } friend std::istream& operator>>(std::istream& is, modint& m) { ll v; return is >> v, m = v, is; } friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); } constexpr uint operator()() const { return m_val; } constexpr modint pow(ull n) const { modint ans = 1; for (modint x = *this; n > 0; n >>= 1, x *= x) { if (n & 1ULL) { ans *= x; } } return ans; } constexpr modint inv() const { return pow(mod - 2); } modint sinv() const { return sinv(m_val); } static modint fact(const uint n) { static std::vector<modint> fs{1, 1}; for (uint i = (uint)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); } return fs[n]; } static modint ifact(const uint n) { static std::vector<modint> ifs{1, 1}; for (uint i = (uint)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); } return ifs[n]; } static modint perm(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k); } static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); } private: static constexpr uint norm(const uint x) { return x < mod ? x : x - mod; } static constexpr uint normll(const ll x) { return norm(uint(x % (ll)mod + (ll)mod)); } static modint sinv(const uint n) { static std::vector<modint> is{1, 1}; for (uint i = (uint)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); } return is[n]; } uint m_val; }; constexpr modinfo modinfo_1000000007 = {1000000007, 5, 1}; constexpr modinfo modinfo_998244353 = {998244353, 3, 23}; using modint_1000000007 = modint<modinfo_1000000007>; using modint_998244353 = modint<modinfo_998244353>; template<typename mint> class fps : public std::vector<mint> { public: using std::vector<mint>::vector; using std::vector<mint>::resize; fps(const std::vector<mint>& vs) : std::vector<mint>{vs} {} int size() const { return std::vector<mint>::size(); } int degree() const { return std::max(0, size() - 1); } fps low(const int n) const { return fps{this->begin(), this->begin() + std::min(n, size())}; } fps rev() const { fps ans = *this; std::reverse(ans.begin(), ans.end()); return ans; } mint& operator[](const int n) { if (size() < n + 1) { resize(n + 1); } return std::vector<mint>::operator[](n); } const mint& operator[](const int n) const { return std::vector<mint>::operator[](n); } mint at(const int n) const { return (n < size() ? (*this)[n] : mint{0}); } fps operator-() const { fps ans = *this; for (auto& v : ans) { v = -v; } return ans; } fps& operator+=(const fps& f) { for (int i = 0; i < f.size(); i++) { (*this)[i] += f[i]; } return *this; } fps& operator-=(const fps& f) { for (int i = 0; i < f.size(); i++) { (*this)[i] -= f[i]; } return *this; } fps& operator*=(const fps& f) { return (*this) = (*this) * f; } fps& operator<<=(const int s) { return *this = (*this << s); } fps& operator>>=(const int s) { return *this = (*this >> s); } fps operator+(const fps& f) const { return fps(*this) += f; } fps operator-(const fps& f) const { return fps(*this) -= f; } fps operator*(const fps& f) const { return mult(f, size() + f.size() - 1); } fps operator<<(const int s) const { fps ans(size() + s); for (int i = 0; i < size(); i++) { ans[i + s] = (*this)[i]; } return ans; } fps operator>>(const int s) const { fps ans; for (int i = s; i < size(); i++) { ans[i - s] = (*this)[i]; } return ans; } friend std::ostream& operator<<(std::ostream& os, const fps& f) { return os << static_cast<std::vector<mint>>(f); } fps derivative() const { fps ans; for (int i = 1; i < size(); i++) { ans[i - 1] = (*this)[i] * i; } return ans; } fps integral() const { fps ans; for (int i = 1; i <= size(); i++) { ans[i] = (*this)[i - 1] * mint{i}.sinv(); } return ans; } fps mult(const fps& f, const int sz) const { if (sz == 0) { return fps{}; } const int N = std::min(size(), sz) + std::min(f.size(), sz) - 1; if (N <= (1 << mint::max2p)) { auto ans = conv<mint>(*this, f, sz); return ans; } else { const auto cs1 = conv<submint1>(*this, f, sz); const auto cs2 = conv<submint2>(*this, f, sz); const auto cs3 = conv<submint3>(*this, f, sz); fps ans((int)cs1.size()); for (int i = 0; i < (int)cs1.size(); i++) { ans[i] = restore(cs1[i](), cs2[i](), cs3[i]()); } return ans; } } fps smult(const int p, const mint a, const int sz) { fps ans = low(sz); for (int i = 0; i + p < sz; i++) { ans[i + p] += (*this)[i] * a; } return ans; } fps sdiv(const int p, const mint a, const int sz) { fps ans = low(sz); for (int i = 0; i + p < sz; i++) { ans[i + p] -= ans[i] * a; } return ans; } fps inv(const int sz) const { const int n = size(); assert((*this)[0]() != 0); const int N = n * 2 - 1; if (N <= (1 << mint::max2p)) { fps r{(*this)[0].inv()}; for (int lg = 0, m = 1; m < sz; m <<= 1, lg++) { fps f{this->begin(), this->begin() + std::min(n, 2 * m)}; fps g = r; f.resize(2 * m), g.resize(2 * m); trans(f, lg + 1, false), trans(g, lg + 1, false); for (int i = 0; i < 2 * m; i++) { f[i] *= g[i]; } trans(f, lg + 1, true); std::fill(f.begin(), f.begin() + m, 0); trans(f, lg + 1, false); for (int i = 0; i < 2 * m; i++) { f[i] *= g[i]; } trans(f, lg + 1, true); for (int i = m; i < std::min(2 * m, sz); i++) { r[i] = -f[i]; } } return r; } else { fps g{(*this)[0].inv()}; for (int lg = 0, m = 1; m < sz; m <<= 1, lg++) { g = fps{2} * g - this->mult(g.mult(g, 2 * m), 2 * m); } return g.low(sz); } } fps log(const int sz) const { assert((*this)[0]() == 1); auto ans = derivative().mult(inv(sz), sz).integral(); ans.resize(sz); return ans; } fps exp(const int sz) const { const int n = size(); if (n == 0) { return fps{1}.low(sz); } assert((*this)[0]() == 0); const int N = n * 2 - 1; if (N <= (1 << mint::max2p)) { fps f = {1, (*this)[1]}, g{1}, G{1, 1}; for (int m = 2, lg = 1; m < sz; m <<= 1, lg++) { auto F = f; F.resize(2 * m), trans(F, lg + 1, false); fps z(m); for (int i = 0; i < m; i++) { z[i] = F[i] * G[i]; } trans(z, lg, true); std::fill(z.begin(), z.begin() + m / 2, 0); trans(z, lg, false); for (int i = 0; i < m; i++) { z[i] *= G[i]; } trans(z, lg, true); for (int i = m / 2; i < m; i++) { g[i] = -z[i]; } G = g, G.resize(m * 2), trans(G, lg + 1, false); auto q = low(m).derivative(); q.resize(m), trans(q, lg, false); for (int i = 0; i < m; i++) { q[i] *= F[i]; } trans(q, lg, true); const auto df = f.derivative(); for (int i = 0; i < m - 1; i++) { q[i] -= df[i]; } q.resize(m * 2); for (int i = 0; i < m - 1; i++) { q[m + i] = q[i], q[i] = 0; } trans(q, lg + 1, false); for (int i = 0; i < m * 2; i++) { q[i] *= G[i]; } trans(q, lg + 1, true), q.pop_back(), q = q.integral(); for (int i = m; i < std::min(size(), m * 2); i++) { q[i] += (*this)[i]; } std::fill(q.begin(), q.begin() + m, 0), trans(q, lg + 1, false); for (int i = 0; i < m * 2; i++) { q[i] *= F[i]; } trans(q, lg + 1, true); for (int i = m; i < 2 * m; i++) { f[i] = q[i]; } } return f.low(sz); } else { fps f{1}; for (int m = 1; m < sz; m <<= 1) { auto g = low(2 * m); g[0] += 1; f.resize(2 * m); g -= f.log(2 * m); g = f.mult(g, 2 * m); for (int i = m; i < std::min(2 * m, g.size()); i++) { f[i] = g[i]; } } return f.low(sz); } } fps pow(const int n, const int sz) const { int p = 0; mint a; for (p = 0; n * p < size(); p++) { if ((*this)[p]() != 0) { a = (*this)[p]; break; } } if (a() == 0) { return fps{}; } fps f = (*this) >> p; for (auto& c : f) { c /= a; } f = f.log(sz - p * n); for (auto& c : f) { c *= n; } f = f.exp(sz - p * n); fps g; for (int i = 0; i < f.size(); i++) { g[i + p * n] = f[i] * a.pow(n); } return g; } fps tshift(const mint c) const { const int N = size(); fps f(N), d(N); for (int i = 0; i < N; i++) { d[i] = c.pow(N - 1 - i) * mint::ifact(N - 1 - i); } for (int i = 0; i < N; i++) { f[i] = (*this)[i] * mint::fact(i); } f = f * d; fps g(N); for (int i = 0; i < N; i++) { g[i] = f[i + N - 1] * mint::ifact(i); } return g; } std::pair<fps, fps> quot_rem(const fps& g) const { const int N = size(), M = g.size(); if (N < M) { return {fps{0}, *this}; } const auto fR = rev(), gR = g.rev(); const auto p = fR.mult(gR.inv(N - M + 1), N - M + 1); const auto q = (*this) - g.mult(p, N); return {p, q.low(M - 1)}; } private: static constexpr modinfo info1 = {469762049, 3, 26}; static constexpr modinfo info2 = {167772161, 3, 25}; static constexpr modinfo info3 = {754974721, 11, 24}; using submint1 = modint<info1>; using submint2 = modint<info2>; using submint3 = modint<info3>; template<typename submint> static void trans(std::vector<submint>& as, const int lg, const bool rev) { const int N = 1 << lg; assert((int)as.size() == N); std::vector<submint> rs, irs; if (rs.empty()) { const submint r = submint(submint::root), ir = r.inv(); rs.resize(submint::max2p + 1), irs.resize(submint::max2p + 1); rs.back() = -r.pow((submint::mod - 1) >> submint::max2p), irs.back() = -ir.pow((submint::mod - 1) >> submint::max2p); for (uint i = submint::max2p; i >= 1; i--) { rs[i - 1] = -(rs[i] * rs[i]), irs[i - 1] = -(irs[i] * irs[i]); } } const auto drange = (rev ? range(0, lg, 1) : range(lg - 1, -1, -1)); for (const int d : drange) { const int width = 1 << d; submint e = 1; for (int i = 0, j = 1; i < N; i += width * 2, j++) { for (int l = i, r = i + width; l < i + width; l++, r++) { const submint x = as[l], y = (rev ? as[r] : as[r] * e); as[l] = x + y, as[r] = (rev ? (x - y) * e : x - y); } e *= (rev ? irs : rs)[lsbp1(j) + 1]; } } if (rev) { const submint iN = submint{N}.inv(); for (auto& a : as) { a *= iN; } } } template<typename submint> static std::vector<submint> conv(const std::vector<mint>& as, const std::vector<mint>& bs, const int sz) { const int M = std::min((int)as.size(), sz) + std::min((int)bs.size(), sz) - 1, lg = clog(M); const int L = 1 << lg; std::vector<submint> As(L), Bs(L); for (int i = 0; i < std::min((int)as.size(), sz); i++) { As[i] = as[i](); } for (int i = 0; i < std::min((int)bs.size(), sz); i++) { Bs[i] = bs[i](); } trans(As, lg, false), trans(Bs, lg, false); for (int i = 0; i < L; i++) { As[i] *= Bs[i]; } trans(As, lg, true); const int N = std::min(sz, (int)as.size() + (int)bs.size() - 1); As.resize(N); return As; } static constexpr submint2 ip1 = submint2{submint1::mod}.inv(); static constexpr submint3 ip2 = submint3{submint2::mod}.inv(); static constexpr submint3 ip1p2 = submint3{submint1::mod}.inv() * submint3{submint2::mod}.inv(); static constexpr mint p1 = mint{submint1::mod}; static constexpr mint p1p2 = mint{submint1::mod} * mint{submint2::mod}; static constexpr mint restore(const int x1, const int x2, const int x3) { const int k0 = x1, k1 = (ip1 * (x2 - k0))(), k2 = (ip1p2 * (x3 - k0) - ip2 * k1)(); return p1p2 * k2 + p1 * k1 + k0; } }; class printer { public: printer() { for (int i = 0; i < 10000; i++) { for (int j = i, t = 3; t >= 0; t--, j /= 10) { m_dict[i * 4 + t] = (j % 10) + '0'; } } } ~printer() { flush(); } template<typename... Args> int ln(const Args&... args) { return dump(args...), put_char('\n'), 0; } template<typename... Args> int el(const Args&... args) { return dump(args...), put_char('\n'), flush(), 0; } private: using ll = long long; using ull = unsigned long long; static constexpr ull TEN(const int d) { return d == 0 ? 1ULL : TEN(d - 1) * 10ULL; } void flush() { fwrite(m_memory, 1, m_tail, stdout), m_tail = 0; } void put_char(const char c) { m_memory[m_tail++] = c; } static constexpr int dn(const ull x) { return x < TEN(10) ? x < TEN(5) ? x < TEN(2) ? x < TEN(1) ? 1 : 2 : x < TEN(3) ? 3 : x < TEN(4) ? 4 : 5 : x < TEN(7) ? x < TEN(6) ? 6 : 7 : x < TEN(8) ? 8 : x < TEN(9) ? 9 : 10 : x < TEN(14) ? x < TEN(12) ? x < TEN(11) ? 11 : 12 : x < TEN(13) ? 13 : 14 : x < TEN(16) ? x < TEN(15) ? 15 : 16 : x < TEN(17) ? 17 : x < TEN(18) ? 18 : 19; } template<typename T> void dump(T v) { if (C - m_tail < 50) { flush(); } if (v < 0) { put_char('-'), v = -v; } const auto d = dn(v); int i = d - 4; for (i = d - 4; i >= 0; i -= 4, v /= 10000) { memcpy(m_memory + m_tail + i, m_dict + (v % 10000) * 4, 4); } memcpy(m_memory + m_tail, m_dict + v * 4 - i, i + 4); m_tail += d; } template<typename T> void dump(const std::vector<T>& vs) { for (int i = 0; i < (int)vs.size(); i++) { if (i > 0) { put_char(' '); } dump(vs[i]); } } template<typename T> void dump(const std::vector<std::vector<T>>& vss) { for (int i = 0; i < (int)vss.size(); i++) { if (i > 0) { put_char('\n'); } dump(vss[i]); } } template<typename T, typename... Args> void dump(const T& v, const Args&... args) { return dump(v), put_char(' '), dump(args...), void(0); } static constexpr int C = 1 << 18; int m_tail = 0; char m_memory[C]; char m_dict[10000 * 4]; } out; class scanner { public: scanner() {} template<typename T> T val() { if (m_tail - m_head < 40) { disk_read(); } char c = get_char(); const bool neg = (c == '-'); if (neg) { c = get_char(); } T ans = 0; while (c >= '0') { ans = ans * T{10} + (c - '0'); c = get_char(); } return (neg ? -ans : ans); } template<typename T> T val(const T offset) { return val<T>() - offset; } template<typename T> std::vector<T> vec(const int n) { return make_v<T>(n, [this]() { return val<T>(); }); } template<typename T> std::vector<T> vec(const int n, const T offset) { return make_v<T>(n, [this, offset]() { return val<T>(offset); }); } template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1) { return make_v<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); }); } template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset) { return make_v<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); }); } template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; } template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; } private: template<typename T, typename F> std::vector<T> make_v(const int n, F f) { std::vector<T> ans; for (int i = 0; i < n; i++) { ans.push_back(f()); } return ans; } char get_char() { return m_memory[m_head++]; } void disk_read() { std::copy(m_memory + m_head, m_memory + m_tail, m_memory); m_tail -= m_head, m_head = 0; m_tail += fread(m_memory + m_tail, 1, C - m_tail, stdin); } static constexpr int C = 1 << 18; int m_head = 0, m_tail = 0; char m_memory[C]; } in; int main() { using mint = modint_998244353; const auto [N, c] = in.tup<int, int>(); fps<mint> as(N); for (auto& a : as) { a.set_raw(in.val<int>()); } const auto bs = as.tshift(mint{c}); std::vector<int> ans(N); for (int i = 0; i < N; i++) { ans[i] = bs.at(i)(); } out.ln(ans); return 0; }