代码

/*
start thinking:
BULB:
result of thinking:

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

start coding:
AC:
*/
#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;
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];
void getRev(int logn, int n) {
  rev[0] = 0;
  for (int i = 1; i < n; i++) 
    rev[i] = rev[i >> 1] >> 1 ^ (i & 1) << (logn - 1);
}

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) {
    int wi = modpow(g, (mod - 1) / i);
    for (int j = 0; j < n; j += i) {
      int ww = 1;
      for (int k = j; k < j + i / 2; k++) {
        ll bar = (ll)f[k + i / 2] * ww;
        f[k + i / 2] = (f[k] - bar) % mod, f[k] = (f[k] + bar) % mod;
        ww = (ll)ww * wi % mod;
      }
    }
  }
  if (sig == -1) {
    // 另一种IDFT，c.f. https://oi-wiki.org/math/poly/fft/#_14
    reverse(f.begin() + 1, f.end());
    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++);
  getRev(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;
}

评测结果