代码

#include<algorithm>
#include<cstdio>
#include<iostream>

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

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

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

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;
}

namespace Poly {
  using Poly_t = int[1<<21|1];

  int l;
  Poly_t F, G, w, to;

  void prework(int N) {
    int lim, rt;
    for (lim = 1, l = -1; lim < N << 1; lim <<= 1, ++l);
    for (int i = 0; i < lim; ++i)
      to[i] = (to[i >> 1] >> 1) | ((i & 1) << l);
    ++l;
    rt = Pow(g, (mod - 1) >> l, mod);
    w[lim >> 1] = 1;
    for (int i = (lim >> 1) + 1; i < lim; ++i)
      w[i] = 1ll * w[i - 1] * rt % mod;
    for (int i = (lim >> 1) - 1; i; --i)
      w[i] = w[i << 1];
  }

  void DFT(int N, int *g) {
    static unsigned long long f[1<<21|1];
    int d = l, t;
    for (int lim = 1; lim < N; lim <<= 1, --d);
    for (int i = 0; i < N; ++i)
      f[i] = g[to[i] >> d];

    for (int m = 1; m < N; m <<= 1)
      for (int j = 0; j < N; j += m << 1)
        for (int k = 0; k < m; ++k) {
          t = f[j | k | m] * w[k | m] % mod;
          f[j | k | m] = f[j | k] - t + mod;
          f[j | k] += t;
        }

    for (int i = 0; i < N; ++i)
      g[i] = f[i] % mod;
  }

  void IDFT(int N, int *f) {
    std::reverse(f + 1, f + N);
    DFT(N, f);
    for (int i = 0, k = mod - (mod - 1) / N; i < N; ++i)
      f[i] = 1ll * f[i] * k % mod;
  }
} // Poly
using namespace Poly;

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

  cin >> N >> M;
  prework(std::max(N, M));
  for (lim = 1; lim <= N + M; lim <<= 1);

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

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

评测结果