代码

#include <bits/stdc++.h>
#ifdef LOCAL
class IO {
public:
    inline int operator()() {
        int x;
        std::cin >> x;
        return x;
    }
    inline void operator()(int x, char c = ' ') {
        std::cout << x << c << std::flush;
    }
} io;
#else
class IO {
private:
    char buffer[1 << 26], *I = buffer, *O = buffer;
public:
    inline int operator()() {
        int x{};
        for (; !isdigit(*I); ++I);
        for (; +isdigit(*I); ++I) x = x * 10 + *I - '0';
        return x;
    }
    inline void operator()(int x, char c = ' ') {
        char ch[10];
        char *s = ch;
        for (; x >= 10; x /= 10)
            *s++ = '0' + x % 10;
        *O++ = '0' + x;
        while (s != ch)
            *O++ = *--s;
        *O++ = c;
    }
    IO() { fread(buffer, 1, sizeof(buffer), stdin); }
    ~IO() { fwrite(buffer, 1, O - buffer, stdout); }
} io;
#endif
constexpr int N = 1 << 20;
constexpr int P = 998244353;
struct mint {
    int x;
    constexpr inline mint(int x = 0) : x(x) {}
    constexpr inline mint operator+(mint o) const { return x + o.x < P ? x + o.x : x + o.x - P; }
    constexpr inline mint operator-(mint o) const { return x - o.x < 0 ? x - o.x + P : x - o.x; }
    constexpr inline mint operator*(mint o) const { return int(uint64_t(x) * o.x % P); }
    constexpr inline mint &operator+=(mint o) { return *this = *this + o; }
    constexpr inline mint &operator-=(mint o) { return *this = *this - o; }
    constexpr inline mint &operator*=(mint o) { return *this = *this * o; }
};
constexpr inline mint pow(mint a, auto x) {
    mint b = 1;
    for (; x; x >>= 1) {
        if (x & 1)
            b *= a;
        a *= a;
    }
    return b;
}
mint w1[N];
mint w2[N];
__attribute__((constructor)) void init() {
    constexpr mint g = pow(mint{3}, P / N);
    constexpr mint h = pow(mint{3}, P / N * (N - 1));
    w1[N / 2] = w2[N / 2] = 1;
    for (int i = N / 2 + 1; i < N; ++i) w1[i] = w1[i - 1] * g;
    for (int i = N / 2 + 1; i < N; ++i) w2[i] = w2[i - 1] * h;
    for (int i = N / 2 - 1; i > 0; --i) w1[i] = w1[i << 1];
    for (int i = N / 2 - 1; i > 0; --i) w2[i] = w2[i << 1];
}
void dft(mint f[], int n) {
    for (int k = n / 2; k; k /= 2)
        for (int i = 0; i < n; i += k + k)
            for (int j = 0; j < k; ++j) {
                mint x = f[i + j];
                mint y = f[i + j + k];
                f[i + j] = x + y;
                f[i + j + k] = (x - y) * w1[k + j];
            }
}
void ift(mint f[], int n) {
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += k + k)
            for (int j = 0; j < k; ++j) {
                mint x = f[i + j];
                mint y = f[i + j + k] * w2[k + j];
                f[i + j] = x + y;
                f[i + j + k] = x - y;
            }
    mint inv = P - (P - 1) / n;
    for (int i = 0; i < n; ++i) f[i] *= inv;
}
struct poly : std::vector<mint> {
    using vec = std::vector<mint>;
    using vec::vec;
    poly &resize(size_t new_size) {
        vec::resize(new_size);
        return *this;
    }
    poly &operator+=(const poly &o) {
        if (size() < o.size()) resize(o.size());
        for (int i = 0; i < o.size(); ++i) (*this)[i] += o[i];
        return *this;
    }
    poly &operator-=(const poly &o) {
        if (size() < o.size()) resize(o.size());
        for (int i = 0; i < o.size(); ++i) (*this)[i] -= o[i];
        return *this;
    }
    poly &operator*=(poly b) {
        poly &a = *this;
        int m = a.size() + b.size() - 1;
        int n = 2 << std::__lg(m - 1);
        dft(a.resize(n).data(), n);
        dft(b.resize(n).data(), n);
        for (int i = 0; i < n; ++i) a[i] *= b[i];
        ift(a.resize(n).data(), n);
        return resize(m);
    }
    poly operator+(const poly &o) const { return poly(*this) += o; }
    poly operator-(const poly &o) const { return poly(*this) -= o; }
    poly operator*(const poly &o) const { return poly(*this) *= o; }
};
int main() {
    poly a(io()+1);
    poly b(io()+1);
    for (auto &i: a) i = io();
    for (auto &i: b) i = io();
    a *= b;
    for (auto &i: a) io(i.x);
}

评测结果