代码

/**
 * 这觉是一分钟也睡不下去了
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 */

#include <bits/stdc++.h>

static const std::size_t io_buf_size = 1 << 24;
#define USE_LL

#define fo(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout);

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

#ifndef __cpp_lib_void_t
namespace std { template <typename...> using void_t = void; }
#endif
template <typename T, typename _ = void> struct is_container : std::false_type {};
template <typename... Ts> struct is_container_helper {};
template <typename T> struct is_container<T, typename std::conditional<false, is_container_helper<
    decltype(std::declval<T>().size()), decltype(std::declval<T>().begin()), decltype(std::declval<T>().end()),
    decltype(std::declval<T>().cbegin()), decltype(std::declval<T>().cend())
>, void>::type> : public std::true_type {};

template <typename T, typename _ = void> struct is_char : std::false_type {};
template <typename T> struct is_char<T, typename std::enable_if<
    std::is_same<T, char>::value || std::is_same<T, unsigned char>::value || std::is_same<T, signed char>::value
>::type> : public std::true_type {};

template <typename T, typename _ = void> struct is_int : std::false_type {};
template <typename T> struct is_int<T, typename std::enable_if<
    !is_char<T>::value && (std::is_integral<T>::value
#ifdef USE_LL
    || std::is_same<T, ll>::value || std::is_same<T, ull>::value
#endif
    )
>::type> : public std::true_type {};

#define FORCE_INLINE __inline__ __attribute__((always_inline))
namespace FastIO {
class In {
    char buf[io_buf_size];
    char *ip1 = buf, *ip2 = buf;
    FORCE_INLINE int gc() {
        return ip1 == ip2 && (ip2 = (ip1 = buf) + fread(buf, 1, io_buf_size, stdin), ip1 == ip2) ? EOF : *ip1++;
    }
    template <typename T> FORCE_INLINE void __RI(T &x) {
        char c; x = 0; bool f = false;
        while (!isdigit(c = gc()) && c != EOF) f |= (c == '-');
        if (c == EOF) [[unlikely]] return;
        while (x = x * 10 + (c ^ '0'), isdigit(c = gc()));
        if (f) x *= -1;
    }
    template <typename T> FORCE_INLINE void __RC(T &x) {
        char c; while (isspace(c = gc())); x = c;
    }
    FORCE_INLINE void __RS(std::string &x) {
        char c; x.clear();
        while (isspace(c = gc()));
        if (c == EOF) [[unlikely]] return;
        while (x.push_back(c), !isspace(c = gc()) && c != EOF);
    }
public:
    In() = default;
    virtual ~In() = default;
    template <typename T>
    FORCE_INLINE typename std::enable_if<is_char<T>::value, In>::type &R(T &x) { return __RC(x), *this; }
    FORCE_INLINE In &R(std::string &x) { return __RS(x), *this; }
    template <typename T, typename U> FORCE_INLINE In &R(std::pair<T, U> &x) { return R(x.first), R(x.second), *this; }
    template <typename T, typename... Args> FORCE_INLINE In &R(T &x, Args &...args) { return R(x), R(args...), *this; }
    template <typename T, typename... Args> FORCE_INLINE In &RA(T *a, std::size_t n) { for (std::size_t i = 0; i < n; ++i) { R(a[i]); } return *this; }
    template <typename T, typename... Args> FORCE_INLINE In &RA(T *a, std::size_t n, Args... args) { for (std::size_t i = 0; i < n; ++i) { RA(a[i], args...); } return *this; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_int<T>::value, In>::type &R(T &x) { return __RI(x), *this; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_container<T>::value, In>::type &R(T &x) { for (auto &i : x) { R(i); } return *this; }
    // template <typename T> FORCE_INLINE typename std::enable_if<std::is_void<std::void_t<decltype(std::declval<T>().read())>>::value, In>::type &R(T &x) { return x.read(), *this; }
    template <typename T> FORCE_INLINE In &operator>>(T &x) { return R(x); }
};
class Out {
    char buf[io_buf_size];
    int op1 = -1, op2 = io_buf_size - 1;
    FORCE_INLINE void pc(const char &x) { if (op1 == op2) [[unlikely]] { flush(); } buf[++op1] = x; }
    template <typename T> FORCE_INLINE void __WI(T _x) {
        typename std::make_unsigned<T>::type x = _x;
        if (_x < 0) pc('-'), x = ~x + 1;
        static char buf[sizeof(T) * 16 / 5];
        static int len = -1;
        static const char digits[201] =
            "0001020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849"
            "5051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";
        while (x >= 100) {
            auto num = (x % 100) * 2; x /= 100;
            buf[++len] = digits[num + 1], buf[++len] = digits[num];
        }
        if (x >= 10) {
            auto num = (x % 100) * 2;
            buf[++len] = digits[num + 1], buf[++len] = digits[num];
        } else {
            buf[++len] = '0' + x;
        }
        while (len >= 0) pc(buf[len--]);
    }
public:
    const char space = ' ', end_line = '\n';
    Out() = default;
    virtual ~Out() { flush(); }
    FORCE_INLINE void flush() { fwrite(buf, 1, op1 + 1, stdout), op1 = -1; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_char<T>::value, Out>::type &W(const T &x) { return pc(x), *this; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_char<T>::value, Out>::type &W(const T *x) { while (*x != '\0') { pc(*(x++)); } return *this; }
    FORCE_INLINE Out &W(const std::string &x) { return W(x.c_str()), *this; }
    template <typename T, typename U> FORCE_INLINE Out &W(const std::pair<T, U> &x) { return WS(x.first), W(x.second), *this; }
    FORCE_INLINE Out &WL() { return W(end_line), *this; }
    template <typename T> FORCE_INLINE Out &WL(const T &x) { return W(x), W(end_line), *this; }
    FORCE_INLINE Out &WS() { return W(space), *this; }
    template <typename T> FORCE_INLINE Out &WS(const T &x) { return W(x), W(space), *this; }
    template <typename T> FORCE_INLINE Out &WA(T *a, std::size_t n) { for (std::size_t i = 0; i < n; i++) { WS(a[i]); } return WL(), *this; }
    template <typename T, typename... Args> FORCE_INLINE Out &W(const T &x, const Args &...args) { return W(x), W(space), W(args...), *this; }
    template <typename T, typename... Args> FORCE_INLINE Out &WS(const T &x, const Args &...args) { return W(x), W(space), W(args...), W(space), *this; }
    template <typename... Args> FORCE_INLINE Out &WL(const Args &...args) { return W(args...), W(end_line), *this; }
    template <typename T, typename... Args> FORCE_INLINE Out &WA(T *a, std::size_t n, Args... args) { for (std::size_t i = 0; i < n; i++) { WA(a[i], args...); } return *this; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_int<T>::value, Out>::type &W(const T &x) { return __WI(x), *this; }
    template <typename T> FORCE_INLINE typename std::enable_if<is_container<T>::value, Out>::type &W(const T &x) {
        for (auto &i : x) { if (is_container<decltype(i)>::value) W(i); else WS(i); } return WL(), *this;
    }
    // template <typename T> FORCE_INLINE typename std::enable_if<std::is_void<std::void_t<decltype(std::declval<T>().write())>>::value, Out>::type &W(const T &x) { return x.write(), (*this); }
    template <typename T> FORCE_INLINE Out &operator<<(const T &x) { return W(x); }
};
class IO : public In, public Out {};
}

FastIO::IO io; using namespace std;

clock_t _timer;
void timer_begin() { _timer = clock(); }
void timer_end(const char *msg) { fprintf(stderr, "%s: %.3fs\n", msg, double(clock() - _timer) / CLOCKS_PER_SEC); }

mt19937 rnd((unsigned)chrono::system_clock::now().time_since_epoch().count());

const int maxn = 4e6 + 5;
const int inf = ~0u >> 2;
const int mod = 998244353;

void cmod(int &x) { if (x >= mod) x -= mod; else if (x < 0) x += mod; }
int Cmod(int x) { return cmod(x), x; }
int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = mul(a, a)) if (b & 1) c = mul(c, a);
    return c;
}
int inv(int x) { return qpow(x, mod - 2); }
int &reduce(int &x) { return x += (x >> 31) & mod; }
const int G = 3;

typedef vector<int> poly;
bool chklim(int n) { return !(n & (n - 1)); }
int getlim(int n) { int m = 1; while (m < n) { m <<= 1; } return m; }
void change(poly &f) {
    static vector<int> T; int n = (int)f.size();
    if ((int)T.size() != n) {
        T.clear(); T.resize(n);
        for (int i = 1; i < n; ++i) T[i] = (T[i >> 1] + n * (i & 1)) >> 1;
    }
    for (int i = 0; i < n; ++i) if (i < T[i]) swap(f[i], f[T[i]]);
}
void grd(poly &f, int n) { f.resize(n); for (int &x : f) io >> x; }
void gwr(const poly &f) { io << f; }

namespace Const {
int W[maxn];
void init(int n) {
    for (int L = 1; L < n; L <<= 1) {
        int o = qpow(G, (mod - 1) / (L + L)), *w = W + L; w[0] = 1;
        for (int i = 1; i < L; ++i) w[i] = mul(w[i - 1], o);
    }
}
}

void func(int &x, int &y, int w) {
    int t = x - y; reduce(t);
    x = x + y; reduce(x -= mod);
    y = mul(t, w);
}

void DFT(poly &f) {
    int n = (int)f.size();
    assert(chklim(n));
    for (int L = n >> 1; L; L >>= 1) {
        for (int *p = f.data(), *W = Const::W + L; p < f.data() + n; p += 2 * L) {
            for (int *a = p, *b = p + L, *w = W; a < p + L; ++a, ++b, ++w) func(*a, *b, *w);
        }
    }
}
void IDFT(poly &f) {
    int n = (int)f.size();
    assert(chklim(n));
    for (int L = 1; L < n; L <<= 1) {
        for (int *p = f.data(), *W = Const::W + L; p < f.data() + n; p += 2 * L) {
            for (int *a = p, *b = p + L, *w = W; a < p + L; ++a, ++b, ++w) {
                int t = mul(*b, *w);
                *b = *a - t; reduce(*b);
                *a = *a + t; reduce(*a -= mod);
            }
        }
    }
}

void gmul(poly &f, poly &g) {
    if (f.size() * g.size() <= 10000) {
        poly h = f; f.resize(h.size() + g.size() - 1); fill(f.begin(), f.end(), 0);
        for (int i = 0; i < int(h.size()); ++i) {
            for (int j = 0; j < int(g.size()); ++j) {
                f[i + j] += mul(h[i], g[j]); reduce(f[i + j] -= mod);
            }
        }
        return;
    }
    int n = (int)f.size() + (int)g.size() - 1, m = getlim(n);
    f.resize(m), g.resize(m);

    timer_begin();
    DFT(f);
    timer_end("FFT #1");

    timer_begin();
    DFT(g);
    timer_end("FFT #2");

    // timer_begin();
    // double_DFT(f, h);
    // timer_end("FFT #1 #2");

    int t = inv(m); for (int i = 0; i < m; ++i) f[i] = mul(mul(f[i], g[i]), t);

    timer_begin();
    IDFT(f);
    timer_end("IFFT #1");
    reverse(f.begin() + 1, f.end());
    
    f.resize(n);
}

poly f, g;

int main() {
    int n, m; io >> n >> m, ++n, ++m;
    timer_begin();
    Const::init(getlim(n + m - 1));
    timer_end("init");
    grd(f, n), grd(g, m);
    gmul(f, g);
    gwr(f);
    return 0;
}

评测结果