Submit Info #11872

Problem Lang User Status Time Memory
Polynomial Taylor Shift cpp Bogdan AC 263 ms 20.78 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 2 ms 0.67 MiB
fft_killer_00 AC 263 ms 20.67 MiB
fft_killer_01 AC 256 ms 20.67 MiB
max_random_00 AC 255 ms 20.67 MiB
max_random_01 AC 256 ms 20.78 MiB
medium_00 AC 2 ms 0.80 MiB
medium_01 AC 5 ms 0.92 MiB
medium_02 AC 5 ms 0.97 MiB
medium_all_zero_00 AC 0 ms 0.75 MiB
medium_c_zero_00 AC 0 ms 0.79 MiB
random_00 AC 238 ms 17.59 MiB
random_01 AC 247 ms 19.28 MiB
random_02 AC 29 ms 2.96 MiB
small_00 AC 2 ms 0.68 MiB
small_01 AC 2 ms 0.72 MiB
small_02 AC 2 ms 0.72 MiB
small_03 AC 0 ms 0.67 MiB
small_04 AC 3 ms 0.67 MiB
small_05 AC 0 ms 0.73 MiB
small_06 AC 2 ms 0.67 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 2 ms 0.67 MiB
small_10 AC 2 ms 0.70 MiB
small_11 AC 2 ms 0.67 MiB
small_12 AC 2 ms 0.68 MiB
small_13 AC 2 ms 0.72 MiB
small_14 AC 3 ms 0.68 MiB
small_15 AC 3 ms 0.68 MiB

#ifdef DEBUG #define _GLIBCXX_DEBUG #endif //#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; const int mod = 998244353; const int root = 646; const int root_1 = 208611436; const int root_pw = 1 << 20; int mult(int a, int b) { return (1LL * a * b) % mod; } int pw(int a, int b) { if (b == 0) return 1; if (b & 1) return mult(a, pw(a, b - 1)); int res = pw(a, b / 2); return mult(res, res); } int sub(int a, int b) { int s = a - b; if (s < 0) s += mod; return s; } int sum(int a, int b) { int s = a + b; if (s >= mod) s -= mod; return s; } void fft(vector<int> &a, bool invert) { int n = (int) a.size(); for (int i = 1, j = 0; i < n; ++i) { int bit = n >> 1; for (; j >= bit; bit >>= 1) j -= bit; j += bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { int wlen = invert ? root_1 : root; for (int i = len; i < root_pw; i <<= 1) wlen = int(wlen * 1ll * wlen % mod); for (int i = 0; i < n; i += len) { int w = 1; for (int j = 0; j < len / 2; ++j) { int u = a[i + j], v = int(a[i + j + len / 2] * 1ll * w % mod); a[i + j] = u + v < mod ? u + v : u + v - mod; a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod; w = int(w * 1ll * wlen % mod); } } } if (invert) { int nrev = pw(n, mod - 2); for (int i = 0; i < n; ++i) a[i] = int(a[i] * 1ll * nrev % mod); } } void poly_mult(vector<int> &a, vector<int> b) { if (min(a.size(), b.size()) < 128) { vector<int> c = a; a.assign(a.size() + b.size() - 1, 0); for (int i = 0; i < c.size(); ++i) { for (int j = 0; j < b.size(); ++j) { a[i + j] = sum(a[i + j], mult(c[i], b[j])); } } return; } int s = a.size() + b.size(); int r = 1; while (r < s) r *= 2; a.resize(r); b.resize(r); fft(a, false); fft(b, false); for (int j = 0; j < r; j++) { a[j] = mult(a[j], b[j]); } fft(a, true); } vector < int > shift(vector < int > poly, int c) { int n = poly.size(); vector < int > inv(n + 1), fact(n + 1), invfact(n + 1); inv[1] = invfact[1] = invfact[0] = fact[0] = fact[1] = 1; for (int i = 2; i <= n; i++) { fact[i] = mult(fact[i - 1], i); inv[i] = mult(inv[mod % i], mod - mod / i); invfact[i] = mult(invfact[i - 1], inv[i]); } for (int i = 0; i < poly.size(); i++) { poly[i] = mult(poly[i], fact[i]); } int val = 1; vector < int > shifting(n); for (int i = 0; i < n; i++) { shifting[n - i - 1] = mult(val, invfact[i]); val = mult(val, c); } poly_mult(poly, shifting); vector < int > ans(n); for (int i = 0; i < n; i++) { ans[i] = mult(poly[n - 1 + i], invfact[i]); } return ans; } int n, c; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); cin >> n >> c; vector < int > poly(n); for (int& c : poly) cin >> c; auto shiftedPoly = shift(poly, c); for (int& v : shiftedPoly) cout << v << " "; cout << '\n'; return 0; }