代码

#include <bits/stdc++.h>

using namespace std;
#define freopen(x)                                                             \
  freopen(x ".in", "r", stdin);                                                \
  freopen(x ".out", "w", stdout)
#define repl(i, t) for (int i = fi[t]; i; i = ne[i])
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define per(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define _r read()
#define readtype long long
typedef long long var;

const int N = 1 << 18;
const double Pi = acos(-1);

struct Node {
  double x, y;
  void init(int t) { x = t >> 15, y = t & 32767; }
  void operator+=(Node t) { x += t.x, y += t.y; }
  Node operator+(Node t) { return (Node){x + t.x, y + t.y}; }
  Node operator-(Node t) { return (Node){x - t.x, y - t.y}; }
  Node operator*(Node t) {
    return (Node){x * t.x - y * t.y, x * t.y + y * t.x};
  }
  Node operator*(double t) { return (Node){x * t, y * t}; }
  Node operator~() { return (Node){x, -y}; }
};

int n, m, p, tot, limit, k;
Node s[N], t[N], f[N], g[N], w[N];
int res[N];

readtype read();
void mul();
void FFT(Node *t, int type);

int main() {
  // freopen("fast");
  n = _r, m = _r, p = 1e9 + 7;
  rep(i, 0, n) f[i].init(_r);
  rep(i, 0, m) g[i].init(_r);
  tot = n + m;
  mul();
  rep(i, 0, tot) printf("%d ", res[i]);
  return 0;
}

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c))
    s |= c == '-', c = getchar();
  while (isdigit(c))
    a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

void mul() {
  for (limit = 1; limit <= tot; limit <<= 1);
  for (int i = 1; i < limit; i <<= 1) {
    w[i] = (Node){1, 0};
    for (int j = 1; j < i; ++j)
      if ((j & 31) == 1) w[i + j] = (Node){cos(Pi * j / i), sin(Pi * j / i)};
      else w[i + j] = w[i + j - 1] * w[i + 1];
  }
  FFT(f, 1), FFT(g, 1);
  for (int i = 0; i < limit; ++i) {
    Node q, f0, f1, g0, g1;
    q = ~f[i ? limit - i : 0], f0 = (f[i] - q) * (Node){0, -0.5},
    f1 = (f[i] + q) * 0.5;
    q = ~g[i ? limit - i : 0], g0 = (g[i] - q) * (Node){0, -0.5},
    g1 = (g[i] + q) * 0.5;
    s[i] = f1 * g1, t[i] = f1 * g0 + f0 * g1 + f0 * g0 * (Node){0, 1};
  }
  FFT(s, -1), FFT(t, -1);
  rep(i, 0, tot) {
    var v1 = (var)(s[i].x / limit + 0.5) % p,
        v2 = (var)(t[i].x / limit + 0.5) % p,
        v3 = (var)(t[i].y / limit + 0.5) % p;
    res[i] = ((v1 << 30) + (v2 << 15) + v3) % p;
  }
}

void FFT(Node *t, int type) {
  if (type == -1) reverse(t + 1, t + limit);
  for (int i = 0, j = 0; i < limit; ++i) {
    if (i > j) swap(t[i], t[j]);
    for (int k = limit >> 1; (j ^= k) < k; k >>= 1);
  }
  for (int i = 1; i < limit; i <<= 1) {
    for (int j = 0; j < limit; j += i << 1) {
      for (int k = j; k < j + i; ++k) {
        Node wn = w[i + k - j] * t[k + i];
        t[k + i] = t[k] - wn, t[k] += wn;
      }
    }
  }
}

评测结果