代码

/*
start thinking:
BULB:
result of thinking:

https://acm.nflsoj.com/problem/50

start coding:
AC:

卡常记录: 预处理所有2^a次单位根
*/
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
template<class T> bool chmin(T& x, const T& y) {
  return x > y ? (x = y, true) : false;
}
template<class T> bool chmax(T& x, const T& y) {
  return x < y ? (x = y, true) : false;
}
bool Mbe;

#define maxn 262155
const int mod = 998244353;
const int g = 3;
const int invg = 332748118;

int modpow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1)
      res = (ll)res * x % mod;
    y >>= 1;
    x = (ll)x * x % mod;
  }
  return res;
}

int rev[maxn], w[maxn], invw[maxn];
void ini(int logn, int n) {
  rev[0] = 0;
  for (int i = 1; i < n; i++) 
    rev[i] = rev[i >> 1] >> 1 ^ (i & 1) << (logn - 1);
  w[0] = invw[0] = 1;
  w[1] = modpow(g, (mod - 1) / n);
  invw[1] = modpow(invg, (mod - 1) / n);
  for (int i = 2; i <= n; i++)
    w[i] = (ll)w[i - 1] * w[1] % mod, invw[i] = (ll)invw[i - 1] * invw[1] % mod;
}

void ntt(vector<int> &f, int n, int sig) {
  for (int i = 0; i < n; i++)
    if (i < rev[i])
      swap(f[i], f[rev[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    for (int j = 0; j < n; j += i) {
      int *wcur = ~sig ? w : invw, stp = n / i;
      for (int k = j; k < j + i / 2; k++) {
        ll bar = (ll)f[k + i / 2] * *wcur;
        f[k + i / 2] = (f[k] - bar) % mod, f[k] = (f[k] + bar) % mod;
        wcur += stp;
      }
    }
  }
  if (sig == -1) {
    int foo = modpow(n, mod - 2);
    for (int i = 0; i < n; i++)
      f[i] = (ll)f[i] * foo % mod;
  }
}

int l, n, m;
vector<int> a, b;

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

bool Med;
int main() {
  fprintf(stderr, "%.2fMB\n", (&Mbe - &Med) / 1048576.0);
  // scanf("%d%d", &n, &m);
  n = read(), m = read(), n++, m++;
  for (l = 0; (1 << l) < n + m - 1; l++);
  ini(l, 1 << l);
  l = 1 << l;
  a.resize(l);
  b.resize(l);
  for (int i = 0; i < n; i++)
    // scanf("%d", &a[i]);
    a[i] = read();
  for (int i = 0; i < m; i++)
    // scanf("%d", &b[i]);
    b[i] = read();
  ntt(a, l, 1);
  ntt(b, l, 1);
  for (int i = 0; i < l; i++)
    a[i] = (ll)a[i] * b[i] % mod;
  ntt(a, l, -1);
  for (int i = 0; i < n + m - 1; i++)
    print((a[i] + mod) % mod), bufo.put(" \n"[i == n + m - 2]);
  bufo.flush();
  return 0;
}

评测结果