代码

/*
Author: Xjrjyy
LANG: C++
PROG: $FileName$
Mail: admin@xjrjyy.cn
Blog: https://blog.xjrjyy.cn/
*/

/**
 * 使用 Complex
 * 避免拷贝
 * 预处理单位根
 * 消除递归
 * 加入快读
 * 同时处理
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <algorithm>
#include <numeric>
using namespace std;
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <cmath>

#define fo(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout); 
#define Size(V) ((int)(V).size())
#define pii pair<int, int>
#define pll pair<ll, ll>

template <typename M, typename N> inline M &umax(M &a, const N &b) { return a = max(a, (M)b); }
template <typename M, typename N> inline M &umin(M &a, const N &b) { return a = min(a, (M)b); }
template <typename M, typename N, typename K> common_type_t<M, K> Pow(M d, N b, K mod) // use long long
{ common_type_t<M, K> a = d, c = 1; for (; b; b >>= 1, (a *= a) %= mod) { if (b & 1) (c *= a) %= mod; } return c; }
template <typename M, typename N> common_type_t<M, N> Inv(M a, N mod) { return Pow(a, mod - 2, mod); }
template <typename M, typename N> common_type_t<M, N> Gcd(M d, N e)
{ common_type_t<M, N> a = d, b = e, c; for (; b; c = a % b, a = b, b = c); return a; }

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template <typename T> void rd(T &x) {
    x = 0; bool f = false; char c = getchar();
    while (!isdigit(c)) f = f || c =='-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x *= (f ? -1 : 1);
}
#if __cplusplus >= 201103L
template <typename T, typename ... Args> void rd(T &x, Args &... args) { rd(x), rd(args...); }
#endif
template <typename T> T rd() { static T x; rd(x); return x; }

const int maxn = (1 << 20) * 2 + 5;
const int maxlgn = 20 + 1 + 5;
const double pi = acos(-1);

template <typename T>
struct Complex {
    T a, b;
    Complex() {}
    Complex(T a, T b) : a(a), b(b) {}
    friend Complex operator+(const Complex& l, const Complex& r) {
        return Complex(l.a + r.a, l.b + r.b);
    }
    friend Complex operator-(const Complex& l, const Complex& r) {
        return Complex(l.a - r.a, l.b - r.b);
    }
    friend Complex operator*(const Complex& l, const Complex& r) {
        return Complex(l.a * r.a - l.b * r.b, l.a * r.b + l.b * r.a);
    }
};

typedef Complex<double> Comp;
const Comp I(0, 1);
uint32_t T[maxn];

void DFT(Comp* f, uint32_t n, bool rev) {
    for (uint32_t i = 0; i < n; ++i)
        if (i < T[i]) swap(f[i], f[T[i]]);
    for (uint32_t l = 1; l < n; l <<= 1) {
        Comp step(cos(pi / l), sin(pi / l));
        if (rev) step.b *= -1;
        for (uint32_t p = 0; p < n; p += l * 2) {
            Comp cur(1, 0);
            for (uint32_t i = p; i < p + l; ++i) {
                Comp x = cur * f[i + l];
                f[i + l] = f[i] - x;
                f[i] = f[i] + x;
                cur = cur * step;
            }
        }
    }
}

uint32_t n, m, N;
Comp a[maxn], c[maxn];

void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *C)
{
    ::n = n, ::m = m;
    for (N = 1; N < n + m + 2; N <<= 1);
    for (uint32_t i = 0; i < N; ++i) T[i] = T[i / 2] / 2 + (i & 1) * N / 2;
    for (uint32_t i = 0; i <= n; ++i) a[i].a = A[i];
    for (uint32_t i = 0; i <= m; ++i) a[i].b = B[i];
    DFT(a, N, false);
    for (uint32_t i = 0; i <= N; ++i) c[i] = a[i] * a[i];
    DFT(c, N, true);
    for (uint32_t i = 0; i <= n + m; ++i) C[i] = (int)(c[i].b / N / 2 + 0.5);
}

评测结果