代码

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> poly;

const int MOD = 998244353;
const int G = 3;

namespace Mod_math {
  inline int Add(int a, int b) {
    return (a += b) > MOD? a - MOD : a;
  }
  inline int Sub(int a, int b) {
    return (a -= b) < 0? a + MOD : a;
  }
  inline int Mul(int a, int b) {
    return (long long)a * b % MOD;
  }
  int Pow(int a, int b) {
    int t = 1;
    for (; b; b >>= 1) {
      if (b & 1) {
        t = Mul(t, a);
      }
      a = Mul(a, a);
    }
    return t;
  }
  int Inv(int x) {
    return Pow(x, MOD - 2);
  }
}

namespace Polynome {
  using namespace Mod_math;

  const int N = (1 << 19) + 5;
  
  int rev[N], w[N];

  void Init(const int L) {
    for (int i = 0; i < L; ++i) {
      rev[i] = rev[i >> 1] >> 1;
      if (i & 1) {
        rev[i] |= L >> 1;
      }
    }
    for (int l = 1; l < L; l <<= 1) {
      w[l] = 1;
      int wl = Pow(G, (MOD - 1) / 2 / l); // 2 * l long !!
      for (int i = l + 1; i < l * 2; ++i) {
        w[i] = Mul(w[i - 1], wl);
      }
    }
  }

  void Dft(poly &po, const int L) {
    for (int i = 0; i < L; ++i) {
      if (i < rev[i]) {
        swap(po[i], po[rev[i]]);
      }
    }
    int a, b, *wx, *l, *r;
    for (int k = 1; k < L; k *= 2) {
      for (int i = 0; i < L; i += k * 2) {
        l = &po[0] + i, r = l + k, wx = w + k;
        for (int j = 0; j < k; ++j) {
          a = *l;
          b = Mul(*wx, *r);
          *l = Add(a, b);
          *r = Sub(a, b);
          ++l, ++r, ++wx;
        }
      }
    }
  }

  void Idft(poly &po, const int L) {
    reverse(po.begin() + 1, po.end());
    Dft(po, L);
    int inv_l = Inv(L);
    for (int i = 0; i < L; ++i) {
      po[i] = Mul(po[i], inv_l);
    }
  }

  poly Multiply(poly f, poly g, int len = -1) {
    int n = f.size(), m = g.size(), l = 1;
    for (; l < n + m - 1; l <<= 1);
    Init(l);
    f.resize(l), Dft(f, l);
    g.resize(l), Dft(g, l);
    for (int i = 0; i < l; ++i) {
      f[i] = Mul(f[i], g[i]);
    }
    Idft(f, l);
    if (len == -1) {
      len = n + m - 1;
    }
    f.resize(len);
    return f;
  }
  
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  ++n, ++m;
  poly f(n), g(m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &f[i]);
  }
  for (int i = 0; i < m; ++i) {
    scanf("%d", &g[i]);
  }
  f = Polynome::Multiply(f, g);
  for (int i = 0; i < f.size(); ++i) {
    printf("%d%c", f[i], " \n"[i == f.size() - 1]);
  }
  return 0;
}

评测结果