代码

/**
 * 这觉是一分钟也睡不下去了
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 一拳把地球打爆！
 * 感觉不如快读。。。优化
 */

#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;
struct IO {
    struct precalc {
        alignas(64) char digit[40000];
        uint64_t log[64][2];
        constexpr precalc() : digit{}, log{} {
            for(int i = 0; i < 10000; i++) {
                digit[i * 4 + 0] = 48 + i / 1000;
                digit[i * 4 + 1] = 48 + i / 100 % 10;
                digit[i * 4 + 2] = 48 + i / 10 % 10;
                digit[i * 4 + 3] = 48 + i % 10;
            }
            int index = 0;
            uint64_t value = 9;
            for(int i = 0; i < 64; i++) {
                // [2^i-1, 2^(i+1)-2]
                log[i][0] = index, log[i][1] = value;
                if((2ULL << i) - 2 > value)
                    index++, value = value <= (UINT64_MAX - 9) / 10 ? value * 10 + 9 : UINT64_MAX;
            }
        }
        inline __attribute((always_inline))
        void store(void* out, uint64_t k)const {
            memcpy(out, digit + k * 4, 4);
        }
    };
    static const int inSZ = 1 << 18;
    char inBuf[inSZ], *in1, *in2;
    inline __attribute((always_inline))
    int read() {
        if(__builtin_expect(in1 > inBuf + inSZ - 32, 0)) {
            auto len = in2 - in1;
            memcpy(inBuf, in1, len);
            in1 = inBuf, in2 = inBuf + len;
            in2 += fread(in2, 1, inSZ - len, stdin);
            if(in2 != inBuf + inSZ) *in2 = 0;
        }
        int res = 0;
        char c;
        while((c = *in1++) < 48);
        while(res = res * 10 + c - 48, (c = *in1++) >= 48);
        return res;
    }
    static const int outSZ = 1 << 22;
    char outBuf[outSZ], *out;
    inline __attribute((always_inline))
    void write(uint64_t x) {
        if(__builtin_expect(out > outBuf + outSZ - 32, 0))
            fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
        static constexpr auto P = precalc();
        uint64_t bsr = __builtin_ia32_bsrdi(x + 1);
        const uint64_t B = 10000, B2 = B * B, B3 = B2 * B, B4 = B3 * B;
        uint64_t len = P.log[bsr][0] + (P.log[bsr][1] < x);
        const uint64_t extra[4] = {1000, 100, 10, 1};
        x *= extra[len & 3];
        switch(len >> 2) {
            case 0: // [0, 9999]
                P.store(out, x);
                break;
            case 1: // [10000, 99999999]
                P.store(out + 4, x - x / B * B);
                P.store(out, x / B);
                break;
            case 2:
                P.store(out + 8, x - x / B * B);
                P.store(out + 4, x / B - x / B2 * B);
                P.store(out, x / B2);
                break;
            default: __builtin_unreachable();
        }
        out += len + 2, out[-1] = ' ';
    }
    IO() {
        in1 = inBuf;
        in2 = in1 + fread(in1, 1, inSZ, stdin);
        out = outBuf;
    }
    ~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} 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 1ull * 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); }
inline 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 grd(poly &f, int n) { f.resize(n); for (int &x : f) x = io.read(); }
void gwr(const poly &f) { for (int x : f) io.write(x); }

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);
    }
}
}

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

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) func2(*a, *b, *w);
        }
    }
}

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");

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

    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; n = io.read(), m = io.read(), ++n, ++m;
    timer_begin();
    Const::init(getlim(n + m));
    timer_end("init");
    grd(f, n), grd(g, m);
    gmul(f, g);
    gwr(f);
    return 0;
}

评测结果