代码

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for (int i = (int)(x); i < (int)(y); ++i)
#define REP(i, x, y) for (int i = (int)(x); i <= (int)(y); ++i)
#define MP make_pair
#define PB push_back
#define PH push
#define fst first
#define snd second
#define y0 yjtakioi0
#define y1 yjtakioi1
#define y2 yjtakioi2
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;

const int SIZ = 524288;
const int INF = 998244353;
const int g = 3;

int btf[SIZ];
int A[SIZ], B[SIZ], C[SIZ], T[SIZ], W[SIZ], IW[SIZ];

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

inline void prepare(int siz) {
  FOR(i, 0, siz)
  btf[i] = (btf[i >> 1] >> 1) + (i & 1) * (siz >> 1);
  int cur = qpow(g, (INF - 1) / siz);
  W[0] = 1;
  FOR(i, 1, siz)
  W[i] = 1ll * W[i - 1] * cur % INF;
  cur = qpow(g, INF - 1 - (INF - 1) / siz);
  IW[0] = 1;
  FOR(i, 1, siz)
  IW[i] = 1ll * IW[i - 1] * cur % INF;
  memset(A, 0, siz * sizeof(int));
  memset(B, 0, siz * sizeof(int));
  return;
}

inline void ntt(int *vec, int siz, int INTT) {
  FOR(i, 0, siz)
  if (i < btf[i])
      swap(vec[i], vec[btf[i]]);

  for (int step = 1; step < siz; step <<= 1) {
    FOR(i, 0, step)
    T[i] = (~INTT ? W[siz / (step << 1) * i] : IW[siz / (step << 1) * i]);
    for (int i = 0; i < siz; i += step << 1) {
      int *p1 = vec + i, *p2 = vec + i + step, *p3 = T;
      for (int j = 0; j < step; ++j, ++p1, ++p2, ++p3) {
        int u = *p1, v = 1ll * (*p2) * (*p3) % INF;
        *p1 = (u + v - (u + v >= INF ? INF : 0));
        *p2 = (u - v + (u - v < 0 ? INF : 0));
      }
    }
  }

  if (!~INTT) {
    int iv = qpow(siz, INF - 2);
    FOR(i, 0, siz)
    vec[i] = 1ll * vec[i] * iv % INF;
  }

  return;
}

class Poly : public vector<int> {
 public:
  inline Poly(int n_ = 1) {
    clear();
    resize(n_);
  }

  inline Poly &operator*=(const Poly &O) {
    int siz = 1;
    for (; siz < size() + O.size() - 1; siz <<= 1)
      ;
    if (1ll * size() * O.size() <= 4096) {
      memset(C, 0, siz * sizeof(int));
      FOR(i, 0, size())
      FOR(j, 0, O.size())(C[i + j] += 1ll * at(i) * O[j] % INF) %= INF;
      resize(siz);
      FOR(i, 0, siz)
      at(i) = C[i];
      return *this;
    }

    prepare(siz);
    FOR(i, 0, size())
    A[i] = at(i);
    FOR(i, 0, O.size())
    B[i] = O[i];
    ntt(A, siz, 1);
    ntt(B, siz, 1);

    FOR(i, 0, siz)
    C[i] = 1ll * A[i] * B[i] % INF;
    ntt(C, siz, -1);

    resize(siz);
    FOR(i, 0, siz)
    at(i) = C[i];
    return *this;
  }
};

class FastIO {
 public:
  static const int LEN = 1 << 24;

  int it, len;
  char buf[LEN];

  FastIO() {
    it = len = 0;
    return;
  }

  inline char get() {
    if (it == len) {
      it = 0;
      len = fread(buf, 1, LEN, stdin);
      if (!len)
        return EOF;
    }
    return buf[it++];
  }

  inline void put(char c) {
    if (it == LEN) {
      fwrite(buf, 1, it, stdout);
      it = 0;
    }
    buf[it++] = c;
    return;
  }

  inline void flush() {
    fwrite(buf, 1, it, stdout);
    return;
  }
} bufi, bufo;

inline int read() {
  int x = 0;
  char c;
  int f = 1;
  for (c = bufi.get(); c != '-' && (c < '0' || c > '9'); c = bufi.get())
    ;
  if (c == '-')
    f = -f;
  else
    x = c - '0';
  for (c = bufi.get(); c >= '0' && c <= '9'; c = bufi.get())
    x += (x << 3) + x + c - '0';
  return x;
}

inline void print(int x) {
  if (x < 0)
    bufo.put('-'), x = -x;
  if (x == 0) {
    bufo.put('0');
    return;
  }
  int stk[15], top = 0;
  for (; x; x /= 10)
    stk[++top] = x % 10;
  for (; top;)
    bufo.put('0' + stk[top--]);
  return;
}

int main() {
  int n, m;
  n = read(), m = read(), n++, m++;
  Poly F(n), G(m);
  FOR(i, 0, n)
    F[i] = read();
  FOR(i, 0, m)
    G[i] = read();

  F *= G;

  FOR(i, 0, n + m - 1)
    print(F[i]), bufo.put(' ');
  bufo.flush();
  return 0;
}

评测结果