Submit Info #51018

Problem Lang User Status Time Memory
Multipoint Evaluation cpp-acl (anonymous) AC 1037 ms 71.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.61 MiB
max_random_00 AC 1037 ms 71.77 MiB
max_random_01 AC 1037 ms 71.77 MiB
random_00 AC 454 ms 50.60 MiB
random_01 AC 370 ms 32.45 MiB
random_02 AC 614 ms 57.67 MiB

// Author: wlzhouzhuan #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pb push_back #define fir first #define sec second #define rep(i, l, r) for (int i = l; i <= r; i++) #define per(i, l, r) for (int i = l; i >= r; i--) #define mset(s, t) memset(s, t, sizeof(s)) #define mcpy(s, t) memcpy(s, t, sizeof(t)) template<typename T1, typename T2> void ckmin(T1 &a, T2 b) { if (a > b) a = b; } template<typename T1, typename T2> void ckmax(T1 &a, T2 b) { if (a < b) a = b; } int read() { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= ch == '-', ch = getchar(); while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar(); return f ? -x : x; } template<typename T> void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } template<typename T> void print(T x, char let) { print(x), putchar(let); } #define poly vector<int> #define SZ(a) int(a.size()) const int mod = 998244353; const int inv2 = (mod + 1) / 2; const int G = 3, Gi = 332748118; int add(int x, int y) { if ((x += y) >= mod) x -= mod; return x; } int sub(int x, int y) { if ((x -= y) < 0) x += mod; return x; } int qpow(int a, int b = mod - 2) { int res = 1; while (b > 0) { if (b & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; b >>= 1; } return res; } namespace Poly { vector<int> Rev, W; int lim, L; void getR(int len) { lim = 1, L = 0; while (lim <= len) lim <<= 1, L++; Rev.resize(lim), W.resize(lim), W[0] = 1; for (int i = 0; i < lim; i++) Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) << L - 1); } void wf(poly &a) { int n = a.size(); for (int i = 0; i < n - 1; i++) a[i] = 1ll * (i + 1) * a[i + 1] % mod; a[n - 1] = 0; } void jf(poly &a) { int n = a.size(); for (int i = n - 1; i >= 1; i--) a[i] = 1ll * a[i - 1] * qpow(i) % mod; a[0] = 0; } void NTT(poly &a, int opt) { for (int i = 0; i < lim; i++) if (i < Rev[i]) swap(a[i], a[Rev[i]]); for (int mid = 1; mid < lim; mid <<= 1) { int Wn = qpow(opt == 1 ? G : Gi, (mod - 1) / (mid << 1)); for (int k = 1; k < mid; k++) W[k] = 1ll * W[k - 1] * Wn % mod; for (int j = 0; j < lim; j += mid << 1) { for (int k = 0; k < mid; k++) { int x = a[j + k], y = 1ll * W[k] * a[j + k + mid] % mod; a[j + k] = add(x, y); a[j + k + mid] = sub(x, y); } } } if (opt == -1) { int linv = qpow(lim); for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * linv % mod; } } poly operator + (poly a, poly b) { int len = max(SZ(a), SZ(b)); a.resize(len), b.resize(len); for (int i = 0; i < len; i++) a[i] = (a[i] + b[i]) % mod; return a; } poly operator * (poly a, poly b) { int len = a.size() + b.size() - 1; getR(len); a.resize(lim), b.resize(lim); NTT(a, 1), NTT(b, 1); for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % mod; NTT(a, -1); a.resize(len); return a; } poly Inv(poly a) { if (SZ(a) == 1) return vector<int> (1, qpow(a[0])); int len = a.size(); poly ta = a; ta.resize((len + 1) / 2); poly tb = Inv(ta); getR(2 * len), a.resize(lim), tb.resize(lim); NTT(a, 1), NTT(tb, 1); for (int i = 0; i < lim; i++) tb[i] = 1ll * tb[i] * (mod + 2 - 1ll * a[i] * tb[i] % mod) % mod; NTT(tb, -1); tb.resize(len); return tb; } poly Sqrt(poly a) { if (SZ(a) == 1) return vector<int> (1, 1); int len = a.size(); poly ta = a; ta.resize((len + 1) / 2); poly tb = Sqrt(ta), sqrb = tb * tb; sqrb.resize(len), sqrb = sqrb + a; for (auto &v: sqrb) v = 1ll * inv2 * v % mod; tb.resize(len), sqrb = sqrb * Inv(tb), sqrb.resize(len); return sqrb; } poly Ln(poly a) { poly ta = a; wf(ta); int len = a.size(); a = ta * Inv(a), jf(a); a.resize(len); return a; } poly Exp(poly a) { if (SZ(a) == 1) return vector<int> (1, 1); int len = a.size(); poly ta = a; ta.resize((len + 1) / 2); poly tb = Exp(ta); tb.resize(len); poly Lnb = Ln(tb); assert(Lnb.size() == len); for (int i = 0; i < len; i++) Lnb[i] = (a[i] - Lnb[i] + mod) % mod; Lnb[0] = (Lnb[0] + 1) % mod; tb = tb * Lnb; tb.resize(len); return tb; } poly mulT(poly a, poly b) { int n = a.size(), m = b.size(); poly res(n - m + 1); if (n - m + 1 <= 50) { for (int i = 0; i < n; i++) { for (int j = 0; j < m && j <= i; j++) { if (i - j <= n - m) res[i - j] = (res[i - j] + 1ll * a[i] * b[j]) % mod; } } return res; } getR(n); reverse(b.begin(), b.end()); a.resize(lim), b.resize(lim); NTT(a, 1), NTT(b, 1); for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % mod; NTT(a, -1); for (int i = m - 1, j = 0; i < n; i++, j++) { res[j] = a[i]; } return res; } poly eval(poly a, poly x) { int n = a.size(), m = x.size(); n = max(n, m), a.resize(n), x.resize(n); vector<poly> T(n << 2), F(n << 2); function<void(int, int, int)> dfs1 = [&](int u, int l, int r) { if (l == r) { T[u] = {1, mod - x[l]}; return ; } int mid = l + r >> 1; dfs1(u << 1, l, mid), dfs1(u << 1 | 1, mid + 1, r); T[u] = T[u << 1] * T[u << 1 | 1]; }; vector<int> ret(m); function<void(int, int, int)> dfs2 = [&](int u, int l, int r) { if (l >= m) return ; if (l == r) { ret[l] = F[u][0]; return ; } int mid = l + r >> 1; F[u << 1] = mulT(F[u], T[u << 1 | 1]); F[u << 1 | 1] = mulT(F[u], T[u << 1]); dfs2(u << 1, l, mid), dfs2(u << 1 | 1, mid + 1, r); }; dfs1(1, 0, n - 1); poly tmp = Inv(T[1]); a.resize(2 * n); F[1] = mulT(a, tmp); // F[1].resize(n); /* reverse(tmp.begin(), tmp.end()); tmp = tmp * a, F[1].resize(n); for (int i = 0; i < n; i++) F[1][i] = tmp[n - 1 + i]; */ dfs2(1, 0, n - 1); return ret; } } using namespace Poly; int main() { int n = read(), m = read(); poly a(n), b(m); for (int i = 0; i < n; i++) a[i] = read(); for (int i = 0; i < m; i++) b[i] = read(); poly t = eval(a, b); for (int i = 0; i < m; i++) print(t[i], '\n'); return 0; }