Submit Info #43021

Problem Lang User Status Time Memory
Log of Formal Power Series cpp RezwanArefin01 AC 257 ms 29.43 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_all_zero_00 AC 232 ms 25.60 MiB
max_random_00 AC 254 ms 29.43 MiB
max_random_01 AC 254 ms 29.34 MiB
max_random_02 AC 256 ms 29.43 MiB
max_random_03 AC 257 ms 29.43 MiB
max_random_04 AC 257 ms 29.43 MiB
near_262144_00 AC 120 ms 15.32 MiB
near_262144_01 AC 119 ms 15.32 MiB
near_262144_02 AC 236 ms 25.33 MiB
random_00 AC 247 ms 27.56 MiB
random_01 AC 251 ms 28.72 MiB
random_02 AC 29 ms 4.21 MiB
random_03 AC 253 ms 28.22 MiB
random_04 AC 239 ms 25.56 MiB
small_degree_00 AC 1 ms 0.68 MiB
small_degree_01 AC 1 ms 0.68 MiB
small_degree_02 AC 1 ms 0.68 MiB
small_degree_03 AC 1 ms 0.68 MiB
small_degree_04 AC 1 ms 0.68 MiB
small_degree_05 AC 2 ms 0.68 MiB
small_degree_06 AC 1 ms 0.68 MiB
small_degree_07 AC 2 ms 0.68 MiB
small_degree_08 AC 1 ms 0.68 MiB
small_degree_09 AC 1 ms 0.67 MiB

#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,ssse3") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; #ifdef __linux__ #define getchar getchar_unlocked #define putchar putchar_unlocked #endif template <class Z> Z getint() { char c = getchar(); bool neg = c == '-'; Z res = neg ? 0 : c - '0'; while (isdigit(c = getchar())) res = res * 10 + (c - '0'); return neg ? -res : res; } template <class Z> void putint(Z a, char c = '\n') { if (a < 0) putchar('-'), a = -a; int d[40], i = 0; do d[i++] = a % 10; while (a /= 10); while (i--) putchar('0' + d[i]); putchar(c); } const int mod = 998244353, g = 3; const int N = 1 << 20; inline int mul(int a, int b) { return (ll) a * b % mod; } inline int Pow(int a, int p) { int ret = 1; while(p) { if(p & 1) ret = (ll) ret * a % mod; a = (ll) a * a % mod; p >>= 1; } return ret; } vector<int> rev; vector<int> w; void prepare(int n) { // n is power of 2 int sz = __builtin_ctz(n); if(rev.size() != n) { rev.assign(n, 0); for(int i = 0; i < n; ++i) { rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1)); } } if(w.size() >= n) return; if(w.empty()) w = {0, 1}; sz = __builtin_ctz(w.size()); w.resize(n); // w[n + i] = w_{2n}^i, n power of 2, i < n while((1 << sz) < n) { int wn = Pow(g, (mod - 1) >> (sz + 1)); for(int i = 1 << (sz - 1); i < (1 << sz); ++i) { w[i << 1] = w[i]; w[i << 1 | 1] = (ll) w[i] * wn % mod; } ++sz; } } void fft(int *p, int n) { prepare(n); for(int i = 1; i < n - 1; ++i) if(i < rev[i]) swap(p[i], p[rev[i]]); for(int h = 1; h < n; h <<= 1) { for(int s = 0; s < n; s += h << 1) { for(int i = 0; i < h; ++i) { int &u = p[s + i], &v = p[s + h + i], t = (ll) v * w[h + i] % mod; v = u - t < 0 ? u - t + mod : u - t; u = u + t >= mod ? u + t - mod : u + t; } } } } /*void mul(int *a, int *b, int *c, int n, int m) { static int f[N], g[N]; int sz = n + m - 1; while(sz & (sz - 1)) sz = (sz | (sz - 1)) + 1; memcpy(f, a, n << 2), memcpy(g, b, m << 2); memset(f + n, 0, sz - n << 2), memset(g + m, 0, sz - n << 2); fft(f, sz), fft(g, sz); for(int i = 0; i < sz; ++i) f[i] = (ll) f[i] * g[i] % mod; reverse(f + 1, f + sz); fft(f, sz); int inv_n = Pow(sz, mod - 2); for(int i = 0; i < sz; ++i) c[i] = (ll) f[i] * inv_n % mod; }*/ // size of b is atleast 2n, a[0] != 0 void polyinv(int *a, int *b, int n) { static int x[N], y[N]; b[0] = Pow(a[0], mod - 2); int sz = 1; while(sz < n) { sz <<= 1; memcpy(x, a, sz << 2); fft(x, sz); memcpy(y, b, sz << 2); fft(y, sz); for(int i = 0; i < sz; ++i) x[i] = mul(x[i], y[i]); reverse(x + 1, x + sz), fft(x, sz); memcpy(x, x + sz / 2, sz << 1); memset(x + sz / 2, 0, sz << 1); fft(x, sz); for(int i = 0; i < sz; ++i) x[i] = mul(x[i], mod - y[i]); reverse(x + 1, x + sz), fft(x, sz); int inv_n2 = Pow(sz, mod - 3); for(int i = sz / 2; i < sz; ++i) b[i] = mul(x[i - sz / 2], inv_n2); } } void polyln(int *a, int *b, int n) { static int c[N], inv[N]; if(inv[1] != 1) { inv[1] = 1; for(int i = 2; i < n; ++i) inv[i] = mul(mod - mod / i, inv[mod % i]); } polyinv(a, c, n); for(int i = 0; i < n; ++i) b[i] = mul(i + 1, a[i + 1]); // mul(b, c, b, n, n); int sz = n + n - 1; while(sz & (sz - 1)) sz = (sz | (sz - 1)) + 1; for(int i = n; i < sz; ++i) c[i] = 0; fft(c, sz), fft(b, sz); for(int i = 0; i < sz; ++i) b[i] = mul(b[i], c[i]); reverse(b + 1, b + sz); fft(b, sz); int inv_n = Pow(sz, mod - 2); for(int i = n - 1; i > 0; --i) b[i] = mul(b[i - 1], mul(inv_n, inv[i])); b[0] = 0; } int a[N], b[N], n; int main() { n = getint<int>(); for(int i = 0; i < n; ++i) a[i] = getint<int>(); polyln(a, b, n); for(int i = 0; i < n; ++i) putint<int>(b[i], " \n"[i == n - 1]); return 0; }