代码

#include<algorithm>
#include<cmath>
#include<cstdio>

static char ibuf[1<<20|1], obuf[1<<20|1], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;

struct IO {
  ~IO() {
    flush();
  }

  char gc() {
    return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20 | 1, stdin)) ? EOF : *p1++;
  }

  void flush() {
    fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
  }

  template<typename T>
  IO operator>>(T &n) {
    n = 0; char c = gc();
    while (c < '0' || c > '9') c = gc();
    while (c >= '0' && c <= '9') n = n * 10 + (c ^ 48), c = gc();
    return *this;
  }

  IO operator<<(char n) {
    if (p3 - obuf == (1 << 20 | 1)) flush();
    *p3++ = n;
    return *this;
  }

  template<typename T>
  IO operator<<(T n) {
    static int stk[41];
    int top = 0;
    do stk[top++] = n % 10 + 48; while (n /= 10);
    while (top) *this << char(stk[--top]);
    return *this;
  }
} cin, cout;

using ll = long long;

constexpr int mod = 998244353, g = 3, invG = 332748118;

inline int Pow(ll b, ll p, ll m) {
  b %= m; ll s = 1 % m;
  for (; p; p >>= 1, b = b * b % m)
    if (p & 1) s = s * b % m;
  return s;
}

int to[1<<21|1], F[1<<21|1], G[1<<21|1];

void NTT(int N, int *a, int type) {
  for (int i = 0; i < N; ++i)
    if (i < to[i]) std::swap(a[i], a[to[i]]);

  ll rt, w, t1, t2;
  for (int m = 1; m < N; m <<= 1) {
    rt = Pow(type == 1 ? g : invG, (mod - 1) / (m << 1), mod);
    for (int j = 0; j < N; j += m << 1) {
      w = 1;
      for (int k = 0; k < m; ++k, w = w * rt % mod) {
        t1 = a[j | k], t2 = w * a[j | k | m] % mod;
        a[j | k] = (t1 + t2) % mod, a[j | k | m] = (t1 - t2 + mod) % mod;
      }
    }
  }

  if (type == -1) {
    ll invN = Pow(N, mod - 2, mod);
    for (int i = 0; i < N; ++i)
      a[i] = a[i] * invN % mod;
  }
}

int main() {
  int N, M, lim, l;

  cin >> N >> M;
  for (lim = 1, l = -1; lim <= N + M; lim <<= 1, ++l);
  for (int i = 0; i < lim; ++i)
    to[i] = (to[i >> 1] >> 1) | ((i & 1) << l);

  for (int i = 0; i <= N; ++i)
    cin >> F[i];
  for (int i = 0; i <= M; ++i)
    cin >> G[i];
  
  NTT(lim, F, 1), NTT(lim, G, 1);
  for (int i = 0; i < lim; ++i)
    F[i] = 1ll * F[i] * G[i] % mod;
  NTT(lim, F, -1);

  for (int i = 0; i <= N + M; ++i)
    cout << F[i] << ' ';
  return 0;
}

评测结果