Submit Info #10992

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp QCFium AC 217 ms 21.65 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
example_01 AC 2 ms 0.67 MiB
fft_killer_00 AC 217 ms 21.65 MiB
fft_killer_01 AC 209 ms 21.65 MiB
max_random_00 AC 211 ms 21.65 MiB
max_random_01 AC 212 ms 21.60 MiB
medium_00 AC 2 ms 0.72 MiB
medium_01 AC 7 ms 0.96 MiB
medium_02 AC 5 ms 0.96 MiB
medium_all_zero_00 AC 2 ms 0.73 MiB
medium_c_zero_00 AC 3 ms 0.76 MiB
random_00 AC 194 ms 19.14 MiB
random_01 AC 202 ms 20.50 MiB
random_02 AC 25 ms 3.01 MiB
small_00 AC 3 ms 0.72 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 2 ms 0.68 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 3 ms 0.67 MiB
small_05 AC 0 ms 0.67 MiB
small_06 AC 3 ms 0.67 MiB
small_07 AC 2 ms 0.68 MiB
small_08 AC 0 ms 0.68 MiB
small_09 AC 2 ms 0.67 MiB
small_10 AC 3 ms 0.67 MiB
small_11 AC 0 ms 0.69 MiB
small_12 AC 11 ms 0.67 MiB
small_13 AC 1 ms 0.72 MiB
small_14 AC 1 ms 0.68 MiB
small_15 AC 1 ms 0.68 MiB

#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } template<int mod, int proot> struct NTT { int get_mod() { return mod; } int pow(int a, int b) { int res = 1; for (; b; b >>= 1) { if (b & 1) res = (int64_t) res * a % mod; a = (int64_t) a * a % mod; } return res; } int inv(int i) { return pow(i, mod - 2); } void ntt(std::vector<int> &a, bool inverse) { int n = a.size(); assert((n & -n) == n); int h = pow(proot, (mod - 1) / n); if (inverse) h = inv(h); 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) { int base = pow(h, n / i / 2); int w = 1; std::vector<int> ws(i); for (int j = 0; j < i; j++) ws[j] = w, w = (int64_t) w * base % mod; for (int j = 0; j < n; j += i << 1) { for (int k = 0; k < i; k++) { int u = a[k + j]; int d = (int64_t) a[k + j + i] * ws[k] % mod; a[k + j] = u + d >= mod ? u + d - mod : u + d; a[k + j + i] = d > u ? u + mod - d : u - d; } } } if (inverse) { int ninv = inv(a.size()); for (auto &i : a) i = (int64_t) i * ninv % mod; } } std::vector<int> conv(const std::vector<int> &a_, const std::vector<int> &b_) { if (!a_.size() || !b_.size()) return {}; std::vector<int> 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] = (int64_t) a[i] * b[i] % mod; ntt(a, true); a.resize(a_.size() + b_.size() - 1); return a; } std::vector<int> self_conv(std::vector<int> a) { 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 = (int64_t) i * i % mod; ntt(a, true); a.resize(n_ + n_ - 1); return a; } }; #define MOD 998244353 NTT<998244353, 3> ntt; int main() { int n = ri(); int c = ri(); int a[n]; for (auto &i : a) i = ri(); std::vector<int> fact(n, 1); for (int i = 1; i < n; i++) fact[i] = (int64_t) fact[i - 1] * i % MOD; std::vector<int> inv(n, 1); inv.back() = ntt.inv(fact.back()); for (int i = n; --i; ) inv[i - 1] = (int64_t) inv[i] * i % MOD; auto r0 = fact; for (int i = 0; i < n; i++) r0[i] = (int64_t) r0[i] * a[i] % MOD; std::vector<int> r1(inv.begin(), inv.end()); int cur = 1; for (int i = 0; i < n; i++) r1[i] = (int64_t) r1[i] * cur % MOD, cur = (int64_t) cur * c % MOD; std::reverse(r1.begin(), r1.end()); auto conved = ntt.conv(r0, r1); for (int i = 0; i < n; i++) printf("%d ",(int)((int64_t) conved[n - 1 + i] * inv[i] % MOD)); puts(""); return 0; }