Submit Info #11405

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp QCFium AC 231 ms 24.11 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
example_01 AC 0 ms 0.64 MiB
fft_killer_00 AC 231 ms 24.11 MiB
fft_killer_01 AC 231 ms 24.11 MiB
max_random_00 AC 228 ms 24.11 MiB
max_random_01 AC 227 ms 24.11 MiB
medium_00 AC 3 ms 0.67 MiB
medium_01 AC 5 ms 0.92 MiB
medium_02 AC 5 ms 0.92 MiB
medium_all_zero_00 AC 2 ms 0.68 MiB
medium_c_zero_00 AC 4 ms 0.77 MiB
random_00 AC 199 ms 20.57 MiB
random_01 AC 216 ms 22.74 MiB
random_02 AC 29 ms 3.23 MiB
small_00 AC 1 ms 0.72 MiB
small_01 AC 1 ms 0.72 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 4 ms 0.72 MiB
small_04 AC 1 ms 0.68 MiB
small_05 AC 1 ms 0.68 MiB
small_06 AC 2 ms 0.68 MiB
small_07 AC 0 ms 0.68 MiB
small_08 AC 0 ms 0.72 MiB
small_09 AC 1 ms 0.71 MiB
small_10 AC 2 ms 0.62 MiB
small_11 AC 0 ms 0.72 MiB
small_12 AC 0 ms 0.72 MiB
small_13 AC 0 ms 0.67 MiB
small_14 AC 1 ms 0.68 MiB
small_15 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } template<int mod> struct ModInt{ int x; ModInt () : x(0) {} ModInt (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {} ModInt &operator += (const ModInt &p){ if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator -= (const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator *= (const ModInt &p) { x = (int64_t) x * p.x % mod; return *this; } ModInt &operator /= (const ModInt &p) { *this *= p.inverse(); return *this; } ModInt &operator ^= (int64_t p) { ModInt res = 1; for (; p; p >>= 1) { if (p & 1) res *= *this; *this *= *this; } return *this = res; } ModInt operator - () const { return ModInt(-x); } ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; } ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator ^ (int64_t p) const { return ModInt(*this) ^= p; } bool operator == (const ModInt &p) const { return x == p.x; } bool operator != (const ModInt &p) const { return x != p.x; } explicit operator int() const { return x; } ModInt &operator = (const int p) { x = p; return *this;} ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } return ModInt(u); } friend std::ostream & operator << (std::ostream &stream, const ModInt<mod> &p) { return stream << p.x; } friend std::istream & operator >> (std::istream &stream, ModInt<mod> &a) { int64_t x; stream >> x; a = ModInt<mod>(x); return stream; } }; // typedef ModInt<1000000007> mint; template<int mod, int proot> struct NTT { // mint version using mint = ModInt<mod>; int get_mod() { return mod; } void ntt(std::vector<mint> &a, bool inverse) const { int n = a.size(); assert((n & -n) == n); mint h = mint(proot) ^ ((mod - 1) / n); if (inverse) h = h.inverse(); for (int i = 0, j = 1; j < n - 1; j++) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if (j < i) std::swap(a[i], a[j]); } for (int i = 1; i < n; i <<= 1) { mint base = h ^ (n / i / 2); mint w = 1; std::vector<mint> ws(i); for (int j = 0; j < i; j++) ws[j] = w, w *= base; for (int j = 0; j < n; j += i << 1) { for (int k = 0; k < i; k++) { mint u = a[k + j]; mint d = a[k + j + i] * ws[k]; a[k + j] = u + d; a[k + j + i] = u - d; } } } if (inverse) { mint ninv = mint(a.size()).inverse(); for (auto &i : a) i *= ninv; } } std::vector<mint> convolve_self(std::vector<mint> a) const { if (!a.size()) return {}; size_t n_ = a.size(); size_t size = 1; for (; size < n_ + n_; size <<= 1); a.resize(size); ntt(a, false); for (auto &i : a) i *= i; ntt(a, true); a.resize(n_ + n_ - 1); return a; } std::vector<mint> convolve(const std::vector<mint> &a_, const std::vector<mint> &b_) const { if (!a_.size() || !b_.size()) return {}; if (&a_ == &b_) return convolve_self(a_); std::vector<mint> a = a_, b = b_; size_t size = 1; for (; size < a_.size() + b_.size(); size <<= 1); a.resize(size); b.resize(size); ntt(a, false); ntt(b, false); for (size_t i = 0; i < size; i++) a[i] *= b[i]; ntt(a, true); a.resize(a_.size() + b_.size() - 1); return a; } }; template<int mod> struct Polynomial { using mint = ModInt<mod>; static constexpr std::pair<int, int> proot_map[] = { {998244353, 3}, {897581057, 3}, {645922817, 3} }; static constexpr int proot_map_size = sizeof(proot_map) / sizeof(*proot_map); static constexpr int get_proot(int index = 0) { return index == proot_map_size ? throw 0 : proot_map[index].first == mod ? proot_map[index].second : get_proot(index + 1); } static constexpr int proot = get_proot(); static NTT<mod, proot> ntt; std::vector<mint> data; Polynomial () = default; Polynomial (const std::vector<mint> &data) : data(data) {} template<class T> Polynomial (const std::vector<T> &data) { this->data.resize(data.size()); for (size_t i = 0; i < data.size(); i++) this->data[i] = data[i]; } void normalize() { while (data.size() && !data.back().x) data.pop_back(); } Polynomial & operator += (const Polynomial &rhs) { data.resize(std::max(data.size(), rhs.data.size())); for (size_t i = 0; i < rhs.size(); i++) data[i] += rhs[i]; return *this; } Polynomial & operator -= (const Polynomial &rhs) { data.resize(std::max(data.size(), rhs.data.size())); for (size_t i = 0; i < rhs.size(); i++) data[i] -= rhs[i]; return *this; } Polynomial & operator *= (const Polynomial &rhs) { data = ntt.convolve(data, rhs.data); return *this; } Polynomial & operator /= (Polynomial rhs) { normalize(); rhs.normalize(); if (data.size() < rhs.data.size()) data = { 0 }; else { int size = data.size() - rhs.data.size() + 1; std::reverse(data.begin(), data.end()); std::reverse(rhs.data.begin(), rhs.data.end()); data.resize(size); rhs.data.resize(size); rhs = rhs.inverse(); data = ntt.convolve(data, rhs.data); data.resize(size); std::reverse(data.begin(), data.end()); } return *this; } Polynomial & operator %= (const Polynomial &rhs) { *this -= *this / rhs * rhs; normalize(); return *this; } Polynomial & operator <<= (mint c) { if (!data.size()) return *this; int n = data.size(); std::vector<mint> fact(n, 1), inv(n); for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i; inv.back() = fact.back().inverse(); for (int i = n; --i; ) inv[i - 1] = inv[i] * i; std::vector<mint> r0 = fact; for (int i = 0; i < n; i++) r0[i] *= data[i]; std::vector<mint> r1 = inv; mint cur = 1; for (int i = 0; i < n; i++) r1[i] *= cur, cur *= c; std::reverse(r1.begin(), r1.end()); data = ntt.convolve(r0, r1); data.erase(data.begin(), data.begin() + n - 1); for (int i = 0; i < n; i++) data[i] *= inv[i]; return *this; } Polynomial operator + (const Polynomial &rhs) const { return Polynomial(*this) += rhs; } Polynomial operator - (const Polynomial &rhs) const { return Polynomial(*this) -= rhs; } Polynomial operator * (const Polynomial &rhs) const { return Polynomial(*this) *= rhs; } Polynomial operator / (const Polynomial &rhs) const { return Polynomial(*this) /= rhs; } Polynomial operator % (const Polynomial &rhs) const { return Polynomial(*this) %= rhs; } Polynomial inverse () const { assert(data.size() && data[0].x); std::vector<mint> res{data[0].inverse()}; for (size_t i = 1; i < data.size(); i <<= 1) { auto next_res = res; next_res.resize(i << 2); ntt.ntt(next_res, false); std::vector<mint> h(data.begin(), data.begin() + std::min<size_t>(data.size(), i + i)); h.resize(i << 2); ntt.ntt(h, false); for (size_t j = 0; j < i << 2; j++) next_res[j] *= next_res[j], next_res[j] *= h[j]; ntt.ntt(next_res, true); next_res.resize(i << 1); for (auto &i : next_res) i = -i; for (size_t j = 0; j < i; j++) next_res[j] += res[j] + res[j]; swap(res, next_res); } res.resize(data.size()); return Polynomial(res); } static std::vector<Polynomial> interplate0_tree(const std::vector<mint> &list) { int n_ = list.size(); int n = 1; for (; n < n_; n <<= 1); std::vector<Polynomial> tree(n << 1, Polynomial({1})); for (int i = 0; i < n_; i++) tree[i + n] = Polynomial({-list[i], 1}); for (int i = n; --i; ) tree[i] = tree[i << 1] * tree[i << 1 | 1]; return tree; } std::vector<mint> eval(const std::vector<mint> &list) const { int q_ = list.size(); auto tree = interplate0_tree(list); int q = tree.size() >> 1; std::vector<Polynomial> res_tree(q << 1); res_tree[1] = *this; for (int i = 1; i < q; i++) { res_tree[i << 1] = tree[i << 1].size() ? res_tree[i] % tree[i << 1] : res_tree[i]; res_tree[i << 1 | 1] = tree[i << 1 | 1].size() ? res_tree[i] % tree[i << 1 | 1] : res_tree[i]; } std::vector<mint> res(q_); for (int i = 0; i < q_; i++) res[i] = res_tree[i + q][0]; return res; } mint & operator [] (int i) { return data[i]; } const mint & operator [] (int i) const { return data[i]; } std::string to_string() const { std::string res = ""; for (int i = 0; i < (int) data.size(); i++) { if (i) res += " "; res += std::to_string(data[i].x); } return res; } size_t size() const { return data.size(); } }; template<int mod> NTT<mod, Polynomial<mod>::proot> Polynomial<mod>::ntt; // typedef Polynomial<998244353> Poly; int main() { int n = ri(); int c = ri(); std::vector<int> a(n); for (auto &i : a) i = ri(); Polynomial<998244353> poly(a); printf("%s\n", (poly <<= c).to_string().c_str()); return 0; }