代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 500005, INF = 1e9 + 7;
const double PI = acos(-1);

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

namespace IO {
  const int L = (1 << 23) + 1;
  char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int qr;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
  inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
  inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
  template <class I> inline void gi (I & x) {
    for (c = gc(); c < '0' || c > '9'; c = gc());
    for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
  }
  template <class I> inline void print (I x) {
    if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
    while (x) qu[++ qr] = x % 10 + '0', x /= 10;
    while (qr) putc (qu[qr --]);
  }
  inline char read () {
    for (c = gc(); c < 'a' || c > 'z'; c = gc());
    return c;
  }
  inline void gs (char *s) {
    int l;
    for (c = gc(); c < 'a' || c > 'z'; c = gc());
    for (l = 0; c <= 'z' && c >= 'a'; c = gc()) s[l] = c, ++l;
    s[l] = 0;
  }
  inline void ps (const char *s) {
    int l = strlen(s), i;
    for (i = 0; i < l; i ++) putc(s[i]);
  }
  struct IOC { ~ IOC () { flush (); } } _ioc_;
}

namespace DU {
  int rev[N];

  struct Comp {
    double x, y;
    inline Comp operator + (const Comp &a) {
      return (Comp) { x + a.x, y + a.y };
    }
    inline Comp operator - (const Comp &a) {
      return (Comp) { x - a.x, y - a.y };
    }
    inline Comp operator * (const Comp &a) {
      return (Comp) { x * a.x - y * a.y, x * a.y + y * a.x };
    }
  } A[N];

  void Fft(Comp *a, int le, int ty) {
    for (int i = 0; i < le; ++i)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < le; i <<= 1) {
      Comp wn = (Comp) { cos(PI / i), ty * sin(PI / i) };
      for (int j = 0; j < le; j += i << 1) {
        Comp w = (Comp) { 1, 0 }, x, y;
        for (int k = 0; k < i; ++k, w = w * wn) {
          x = a[j + k]; y = a[j + i + k] * w;
          a[j + k] = x + y; a[j + i + k] = x - y;
        }
      }
    }
  }
  void Multiply(vector<int> &a, vector<int> &b, vector<int> &c) {
    int n = (int)a.size(), m = (int)b.size();
    c.resize(n + m - 1);
    static int L;
    for (L = 1; L < n + m - 1; L <<= 1);
    for (int i = 0; i < L; ++i)
      rev[i] = (rev[i >> 1] >> 1) | (i & 1? L >> 1 : 0);
    for (int i = 0; i < L; ++i) A[i] = (Comp) { 0, 0 };
    for (int i = 0; i < n; ++i) A[i].x = (int)a[i];
    for (int i = 0; i < m; ++i) A[i].y = (int)b[i];
    Fft(A, L, 1);
    for (int i = 0; i < L; ++i) A[i] = A[i] * A[i];
    Fft(A, L, -1);
    for (int i = 0; i < n + m - 1; ++i) c[i] = (int)(A[i].y / L / 2 + 0.3);
  }
}


int main() {
  IO::gi(n), IO::gi(m);
  ++n; ++m;
  a.resize(n);
  b.resize(m);
  for (int i = 0; i < n; ++i) {
    IO::gi(a[i]);
  }
  for (int i = 0; i < m; ++i) {
    IO::gi(b[i]);
  }
  DU::Multiply(a, b, c);
  for (int i = 0; i < (int)c.size(); ++i) {
    IO::print(c[i]); IO::putc(' ');
  }

  return 0;
}

评测结果