代码

/*
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;

bool Med;
int main() {
  fprintf(stderr, "%.2fMB\n", (&Mbe - &Med) / 1048576.0);
  scanf("%d%d", &n, &m), 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]);
  for (int i = 0; i < m; i++)
    scanf("%d", &b[i]);
  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++)
    printf("%d%c", (a[i] + mod) % mod, " \n"[i == n + m - 2]);
  return 0;
}

评测结果