#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)
#define ull unsigned long long
const int maxn = 1 << 18;
const int mod = 998244353, g = 3;
int qp(int x, int n) { return !n ? 1 : 1LL * qp(1LL * x * x % mod, n >> 1) * (n & 1 ? x : 1) % mod; }
int inv(int a) { return qp(a, mod - 2); }
int r[maxn], w[20][maxn];
void init_FFT(int n) {
for (int i = 1; i < n - 1; ++ i) r[i] = r[i >> 1] >> 1 | ((i & 1) * (n >> 1));
for (int x = 2, i = 1; x <= n; x <<= 1, ++ i) {
int wn = qp(g, (mod - 1) / x); w[i][0] = 1;
rep(j, x / 2) w[i][j + 1] = 1LL * w[i][j] * wn % mod;
}
}
inline void FFT(int *a, int n, int f) {
static const ull mod2 = 1ull * mod * mod;
for (int i = 1; i < n - 1; ++ i)
if (i < r[i]) swap(a[i], a[r[i]]);
static ull temp[maxn];
rep(i, n) temp[i] = a[i];
for (int h = 2, x = 1; h <= n; h <<= 1, ++ x) {
for (int i = 0; i < n; i += h) {
int *wn = w[x];
ull *p = temp + i, *q = temp + i + h / 2;
for (int j = 0; j < h / 2; ++ j, ++ p, ++ q, ++ wn) {
ull u = (*p), v = (*q) % mod * (*wn);
(*p) = u + v; (*q) = u + mod2 - v;
}
}
}
rep(i, n) a[i] = temp[i] % mod;
if (!~f) {
reverse(a + 1, a + n);
int r = inv(n);
rep(i, n) a[i] = 1LL * a[i] * r % mod;
}
}
struct poly : vector <int> {
poly(int len, int x = 0) { resize(len); rep(i, len) at(i) = x; }
poly(const vector <int> &v) { *this = v; }
friend inline poly operator + (const poly &a, const poly &b) {
poly c(max(a.size(), b.size()));
rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
rep(i, b.size()) c[i] = (c[i] + b[i]) % mod;
return c;
}
friend inline poly operator - (const poly &a, const poly &b) {
poly c(max(a.size(), b.size()));
rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
rep(i, b.size()) c[i] = (c[i] + mod - b[i]) % mod;
return c;
}
friend inline poly operator * (int c, const poly &a) {
poly b(a.size());
rep(i, a.size()) b[i] = 1LL * c * a[i] % mod;
return b;
}
friend inline poly operator * (const poly &a, const poly &b) {
static int A[maxn], B[maxn];
int n = a.size() + b.size() - 1;
int sz = 1; while (sz < n) sz <<= 1;
init_FFT(sz);
rep(i, sz) A[i] = i < (int)a.size() ? a[i] : 0;
rep(i, sz) B[i] = i < (int)b.size() ? b[i] : 0;
FFT(A, sz, 1); FFT(B, sz, 1);
rep(i, sz) A[i] = 1LL * A[i] * B[i] % mod;
FFT(A, sz, -1);
poly c(n); rep(i, n) c[i] = A[i];
return c;
}
friend poly deri(const poly &a) {
poly b(a.size());
rep(i, a.size()) if (i) b[i - 1] = 1LL * a[i] * i % mod;
return b;
}
friend poly inte(const poly &a) {
poly b(a.size() + 1);
rep(i, b.size()) if (i) b[i] = 1LL * a[i - 1] * inv(i) % mod;
return b;
}
friend poly inv(const poly &a) {
if (a.size() == 1) return poly(1, inv(a[0]));
int n0 = (a.size() + 1) >> 1;
poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = inv(a0);
poly res = a0 * (poly(1, 2) - a0 * a); res.resize(a.size());
return res;
}
friend poly sqrt(const poly &a) {
if (a.size() == 1) return poly(1, 1);
int n0 = (a.size() + 1) >> 1;
poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = sqrt(a0);
poly a1(a.size()); rep(i, n0) a1[i] = a0[i];
poly res = ((mod + 1) / 2) * (a0 + a * inv(a1)); res.resize(a.size());
return res;
}
friend poly ln(const poly &a) {
return inte(deri(a) * inv(a));
}
friend poly exp(const poly &a) {
if (a.size() == 1) return poly(1, 1);
int n0 = (a.size() + 1) >> 1;
poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = exp(a0);
poly a1(a.size()); rep(i, n0) a1[i] = a0[i];
poly res = a0 * (poly(1, 1) - ln(a1) + a); res.resize(a.size());
return res;
}
friend ostream& operator << (ostream &out, const poly &a) {
out << "{";
rep(i, a.size()) out << a[i] << ",}"[i + 1 == (int)a.size()];
return out;
}
};
int main() {
int n; scanf("%d", &n); ++ n;
int m; scanf("%d", &m); ++ m;
poly a(n), b(m);
rep(i, n) scanf("%d", &a[i]);
rep(i, m) scanf("%d", &b[i]);
poly c = a * b;
rep(i, n + m - 1) printf("%d%c", c[i], " \n"[i + 1 == n + m - 1]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 41.43 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 61.082 ms | 9 MB + 52 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 28.383 ms | 4 MB + 160 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 28.433 ms | 4 MB + 148 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 42.26 us | 68 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 41.04 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 39.87 us | 64 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 53.382 ms | 8 MB + 540 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 53.304 ms | 8 MB + 540 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 45.683 ms | 8 MB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 61.534 ms | 9 MB + 132 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 61.46 ms | 8 MB + 12 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 37.86 us | 52 KB | Accepted | Score: 0 | 显示更多 |