代码

#include <bits/stdc++.h>

#define IL inline
#define CT const
#define RG register
#define TT template <typename Ty>

namespace io {
const int MaxBuff = 1 << 24, MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b, buff[MaxOut], *iter = buff;
FILE *_IN = stdin, *_OUT = stdout;
IL char gc() { return S == T && (T = (S = b) + fread(b, 1, MaxBuff, _IN), S == T) ? 0 : *S++; }
IL void pc(const char s) { *iter++ = s; }
IL void fflush() { fwrite(buff, 1, iter - buff, _OUT), iter = buff, fclose(_IN), fclose(_OUT); }
} // namespace io

TT IL Ty max(CT Ty& a, CT Ty& b) { return a > b ? a : b; }
TT IL Ty min(CT Ty& a, CT Ty& b) { return a < b ? a : b; }
TT IL void cmax(Ty& a, CT Ty& b) { if (b > a) a = b; }
TT IL void cmin(Ty& a, CT Ty& b) { if (b < a) a = b; }
TT IL void swap(Ty& a, Ty& b) { Ty t = a; a = b; b = t; }
TT IL void swap(Ty*& a, Ty*& b) { Ty *t = a; a = b; b = t; }

TT IL void read(Ty& t) {
    t = 0; int f = 1; RG char ch = io::gc();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = io::gc(); }
    do { t = t * 10 + ch - '0'; ch = io::gc(); } while (ch >= '0' && ch <= '9'); t *= f;
}

TT IL void write(Ty x) {
    if (x < 0) io::pc('-');
    if (x > 9) write(x / 10);
    io::pc(x % 10 + '0');
}

template <int N, int MOD> 
class NTT {
	public:
  void dit(int n, int *a) {
    for (int m = 1; m < n; m <<= 1) {
      int64_t root = power(G, (MOD - 1) / (m << 1));
      twiddles[0] = 1;
      for (int i = 1; i < m; ++i) {
        twiddles[i] = twiddles[i - 1] * root % MOD;
      }
      for (int i = 0; i < n; i += m << 1) {
        for (int r = i; r < i + m; ++r) {
          int tmp = static_cast<int64_t>(twiddles[r - i]) * a[r + m] % MOD;
          a[r + m] = a[r];
          add(a[r + m], MOD - tmp);
          add(a[r], tmp);
        }
      }
    }
  }

  void dif(int n, int *a) {
    for (int m = n; m >>= 1;) {
      int64_t root = power(G, MOD - 1 - (MOD - 1) / (m << 1));
      twiddles[0] = 1;
      for (int i = 1; i < m; ++i) {
        twiddles[i] = twiddles[i - 1] * root % MOD;
      }
      for (int i = 0; i < n; i += m << 1) {
        for (int r = i; r < i + m; ++r) {
          int tmp = a[r];
          add(tmp, MOD - a[r + m]);
          add(a[r], a[r + m]);
          a[r + m] = static_cast<int64_t>(twiddles[r - i]) * tmp % MOD;
        }
      }
    }
  }

  void convolute(int n, int *a, int *b, int *out) {
    dif(n, a);
    dif(n, b);
    unsigned long long inv_n = power(n, MOD - 2);
    for (int i = 0; i < n; ++i) {
      out[i] = inv_n * a[i] % MOD * b[i] % MOD;
    }
    dit(n, out);
  }

  static int power(int a, int n) {
    int res = 1;
    while (n) {
      if (n & 1) {
        res = 1ULL * res * a % MOD;
      }
      a = 1ULL * a * a % MOD;
      n >>= 1;
    }
    return res;
  }

  static void add(int &x, int a) {
    x += a;
    if (x >= MOD) {
      x -= MOD;
    }
  }

private:
  void revbin(int n, int *a) {
    for (int i = 1, j = 0; i < n - 1; ++i) {
      for (int s = n; j ^= s >>= 1, ~j & s;)
        ;
      if (i < j) {
        std::swap(a[i], a[j]);
      }
    }
  }

  static const int G = 3;
  int twiddles[N];
};

const int N = 1e6 + 5;
int n, m, a[N * 4], b[N * 4], c[N * 4];
NTT<N * 4, 998244353> ntt;

int main() {
    read(n), read(m); ++n, ++m;
    for (int i = 0; i < n; ++i) read(a[i]);
    for (int i = 0; i < m; ++i) read(b[i]);
    int n2 = 1;
  	while (m + n >= n2) n2 <<= 1;
		ntt.convolute(n2, a, b, c);
    for (int i = 0; i < n + m - 1; ++i) write(c[i]), io::pc(' ');
    io::pc('\n');
    io::fflush();
    return 0;
}

评测结果