代码

#include <bits/stdc++.h>

struct IO {
  const static int S = 1e8;
  char buc_in[S], buc_out[S],
    *p_in = buc_in, *p_out = buc_out;
  IO() { fread(buc_in, 1, S, stdin); }
  ~IO() { fwrite(buc_out, 1, p_out - buc_out, stdout); }
  inline int rd() {
    int b = 0;
    while (!isdigit(*p_in)) ++p_in;
    while (isdigit(*p_in)) b = b * 10 + *p_in++ - '0';
    return b;
  }
  inline void out(int x) {
    static char buc[10], *p = buc;
    do *p++ = x % 10 + '0';
    while (x /= 10);
    while (p != buc)
      *p_out++ = *--p;
    *p_out++ = ' ';
  }
} io;

const int N = 3e5 + 233, P = 998244353;

inline int fpow(int x, int y) {
  int ret = 1;
  for ( ; y; y >>= 1, x = 1ll * x * x % P)
    if (y & 1) ret = 1ll * ret * x % P;
  return ret;
}

const int Gp = 3, Gpi = fpow(Gp, P - 2);

int rev[N], lim, L, inv_lim;

inline void init(int n) {
  L = 0, lim = 1;
  while (lim < n) lim <<= 1, ++L;
  for (int i = 1; i < lim; ++i) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
  }
  inv_lim = fpow(lim, P - 2);
}

inline void DFT(int f[], int o) {
  for (int i = 0; i < lim; ++i)
    if (i < rev[i])
      std::swap(f[i], f[rev[i]]);
  for (int i = 1; i < lim; i <<= 1) {
    int T = fpow(o == 1 ? Gp : Gpi, (P - 1) / (i << 1));
    for (int j = 0; j < lim; j += i << 1) {
      int w = 1;
      for (int k = 0; k < i; ++k, w = 1ll * w * T % P) {
        int nx = f[j + k], ny = 1ll * f[i + j + k] * w % P;
        f[j + k] = nx + ny - P, f[j + k] += f[j + k] < 0 ? P : 0;
        f[i + j + k] = nx - ny, f[i + j + k] += f[i + j + k] < 0 ? P : 0;
      }
    }
  }
  if (o == -1)
    for (int i = 0; i < lim; ++i)
      f[i] = 1ll * f[i] * inv_lim % P;
}

int n, m, A[N], B[N];

int main() {
  n = io.rd(), m = io.rd();
  for (int i = 0; i <= n; ++i)
    A[i] = io.rd();
  for (int i = 0; i <= m; ++i)
    B[i] = io.rd();
  init(n + m + 1);
  DFT(A, 1), DFT(B, 1);
  for (int i = 0; i < lim; ++i)
    A[i] = 1ll * A[i] * B[i] % P;
  DFT(A, -1);
  for (int i = 0; i <= n + m; ++i)
    io.out(A[i]);
  return 0;
}

评测结果