代码

#include <bits/stdc++.h>
namespace staring
{
    using namespace std;
    using LL = long long;
    using ULL = unsigned long long;

    template <typename TYPE>
    int gmax(TYPE &x, const TYPE &y) {return x < y ? x = y, 1 : 0;}
    template <typename TYPE>
    int gmin(TYPE &x, const TYPE &y) {return y < x ? x = y, 1 : 0;}

    static constexpr int SIZE = 1 << 20;
    static char buffin[SIZE]{}, *pin1{}, *pin2{};
    static char buffout[SIZE]{}, *pout{buffout};
    static FILE *fin = stdin, *fout = stdout;

    #define GETC (pin1 == pin2 && (pin2 = (pin1 = buffin) + fread(buffin, 1, SIZE, fin), pin1 == pin2) ? EOF : *pin1++)
    #define PUTC (pout - buffout == SIZE && (fwrite(buffout, SIZE, 1, fout), pout = buffout), *pout++)

    void fileO(string file)
    {
        if (file.empty()) return;
        fin = fopen((file + ".in").c_str(), "r");
        fout = fopen((file + ".out").c_str(), "w");
    }
    int fileC()
    {
        fwrite(buffout, pout - buffout, 1, fout);
        if (fin != stdin) fclose(fin), fclose(fout);
        return 0;
    }
    
    template <typename TYPE>
    void read(TYPE &x)
    {
        #define isdigit(c) (c >= 48 && c <= 57)
        static int signf{0}, chin{0};
        x = signf = 0, chin = GETC;
        while (!isdigit(chin)) signf |= chin == '-', chin = GETC;
        while (isdigit(chin)) x = (x << 3) + (x << 1) + (chin & 15), chin = GETC;
        if (signf) x = -x;
        #undef isdigit
    }
    template <>
    void read(string &s)
    {
        #define isspace(c) (c <= 31 || c == 127)
        static char chin{0}; s = "";
        while (isspace(chin)) chin = GETC;
        while (!isspace(chin)) s += chin, chin = GETC;
        #undef isspace
    }
    template <typename TYPE, typename... TYPEs>
    void read(TYPE &x, TYPEs &...xs)
    {
        read(x), read(xs...);
    }

    template <typename TYPE>
    void write(TYPE x, char ch = '\n')
    {
        static int stack[64]{}, top{0};
        !x && (PUTC = '0'), x < 0 && (x = -x, PUTC = '-');
        while (x) stack[top ++] = x % 10, x /= 10;
        while (top) PUTC = stack[--top] | 48;
        if (ch) PUTC = ch;
    }
    template <>
    void write(string s, char ch)
    {
        for (char c : s) PUTC = c;
        if (ch) PUTC = ch;
    }
    template <typename TYPE, typename... TYPEs>
    void write(TYPE x, TYPEs ...xs)
    {
        write(x, ' '), write(xs...);
    }

    #undef GETC
    #undef PUTC

    void mainSolve();

}using namespace staring;
int main()
{
    fileO("");
    int testCount = 1;
    // read(testCount);
    while (testCount --)
        mainSolve();
    return fileC();
}

namespace moduleInteger
{
    // edited by staring
    // link: https://www.luogu.com.cn/user/642907

    using i32 = int;
    using u32 = unsigned int;
    using i64 = long long;
    using u64 = unsigned long long;
    using i128 = __int128;
    using u128 = unsigned __int128;

    struct Barrett
    {
        u32 _m; u64 im;
        explicit Barrett(u32 m)
            : _m(m), im(u64(-1) / m + 1){};
        u32 mod(u64 x)
        {
            if(x < _m) return x;
            u64 y = u64(u128(x) * im >> 64);
            u64 z = y * _m;
            return u32(x >= z ? x - z : x - z + _m);
        }
        u32 inv(u32 a)
        {
            u32 r = 1;
            while(a > 1)
            {
                u32 t = _m / a;
                r = mod(u64(r) * (_m - t));
                a = _m - t * a;
            }
            return r;
        }
    };

    template<i32 P>
    struct MODINT
    {
        using mi = MODINT;

        private:

        i32 x;
        static Barrett bt;

        public:

        constexpr MODINT() : x(0){}
        constexpr MODINT(i32 _x) : x(_x) {}
        // constexpr MODINT(i32 _x, std::nullptr_t) : x(_x) {}
        // constexpr MODINT(i64 _x) : x(normal(bt.mod(_x))) {}
        
        constexpr i32 normal(i32 x)
            {return x >= P ? x - P : x + (x >> 31 & P);}
        constexpr i32 val() const {return x;}
        constexpr static i32 mod() {return P;}
        constexpr explicit operator bool() const {return x;}

        constexpr mi operator-() const {return mi(x ? P - x : 0);}
        constexpr mi& operator+=(const mi& rhs) {x = normal(x + rhs.val()); return *this;}
        constexpr mi& operator-=(const mi& rhs) {x = normal(x - rhs.val()); return *this;}
        constexpr mi& operator++() {return (*this) += 1;}
        constexpr mi& operator--() {return (*this) -= 1;}
        constexpr mi& operator*=(const mi& rhs) {x = bt.mod(u64(x) * rhs.val()); return *this;}
        constexpr mi& operator/=(const mi& rhs) {return *this *= rhs.inv();}
        constexpr mi inv() const
        {
            assert(x != 0);
            return mi(bt.inv(x));
        }
        constexpr mi pow(i64 b) const
        {
            mi a = *this, c = 1;
            if(b < 0) a = a.inv(), b = -b;
            while(b)
            {
                if(b & 1) c *= a;
                a *= a, b >>= 1;
            }
            return c;
        }
        constexpr mi sqr() const
        {
            if(!this->val()) return 0;
            if(this->val() == 1) return 1;
            assert(this->pow(P - 1 >> 1) == 1);

            mi a;
            do a = rand() % P;
            while((a * a - *this).pow(P - 1 >> 1) != P - 1);
            mi i2 = a * a - *this;
            auto mul = [&i2](const std::pair <mi, mi> &a, const std::pair <mi, mi> &b)
                {return std::make_pair(a.first * b.first + a.second * b.second * i2,
                    a.first * b.second + a.second * b.first);};
            std::pair <mi, mi> x = {a, 1}, z = {1, 0};
            for(i32 y = P + 1 >> 1; y; y >>= 1, x = mul(x, x))
                if(y & 1) z = mul(x, z);
            return std::min(z.first.val(), P - z.first.val());
        }

        constexpr friend mi operator+(const mi& lhs, const mi& rhs)
            {auto res = lhs; res += rhs; return res;}
        constexpr friend mi operator-(const mi& lhs, const mi& rhs)
            {auto res = lhs; res -= rhs; return res;}
        constexpr friend mi operator*(const mi& lhs, const mi& rhs)
            {auto res = lhs; res *= rhs; return res;}
        constexpr friend mi operator/(const mi& lhs, const mi& rhs)
            {auto res = lhs; res /= rhs; return res;}
        constexpr friend mi operator++(mi& x, i32)
            {auto res = x; x += 1; return res;}
        constexpr friend mi operator--(mi& x, i32)
            {auto res = x; x -= 1; return res;}
        
        constexpr friend std::istream& operator>>(std::istream& is, mi& x)
            {u64 v; is >> v; x = v; return is;}
        constexpr friend std::ostream& operator<<(std::ostream& os, const mi& x)
            {os << x.val(); return os;}
        constexpr bool operator==(const mi& rhs) const {return x == rhs.val();}
        constexpr bool operator!=(const mi& rhs) const {return x != rhs.val();}
    };

    template<i32 P> Barrett MODINT<P>::bt(P);
}

namespace polyNomial
{
    // edited by staring
    // link: https://www.luogu.com.cn/user/642907
    // module number 998244353

    using namespace moduleInteger;
    constexpr i32 MOD = 998244353;
    using mi = MODINT<MOD>;
    using vmi = std::vector <mi>;
    constexpr mi G = 3, I = 911660635;
    constexpr mi omega[] = {1, 998244352, 911660635, 372528824, 929031873,
                            452798380, 922799308, 781712469, 476477967, 166035806,
                            258648936, 584193783, 63912897, 350007156, 666702199,
                            968855178, 629671588, 24514907, 996173970, 363395222,
                            565042129, 733596141, 267099868, 15311432, 3748461};
    
    struct POLY : vmi
    {
        using pl = POLY;

        private:

        template <const i32 n> constexpr
        void DIF(const POLY::iterator& a)
        {
            constexpr i32 m = n >> 1, l = n >> 2;
            mi w1 = 1, w0 = omega[__builtin_ctz(n)];
            for(i32 i = 0; i < l; i ++, w1 *= w0)
            {
                mi x = a[i], y = a[i | l];
                mi z = a[i | m], w = a[i | m | l];
                a[i] = x + z;
                a[i | l] = y + w;
                a[i | m] = w1 * (x - z + (y - w) * I);
                a[i | m | l] = w1 * w1 * w1 * (x - z - (y - w) * I);
            }
            DIF<m>(a), DIF<l>(a + m), DIF<l>(a + m + l);
        }

        constexpr void DFT();

        template <const i32 n> constexpr
        void DIT(const POLY::iterator& a)
        {
            constexpr i32 m = n >> 1, l = n >> 2;
            DIT<m>(a), DIT<l>(a + m), DIT<l>(a + m + l);
            mi w1 = 1, w0 = omega[__builtin_ctz(n)];
            for(i32 i = 0; i < l; i ++, w1 *= w0)
            {
                mi x = a[i], y = a[i | l];
                mi z = w1 * a[i | m], w = w1 * w1 * w1 * a[i | m | l];
                a[i] = x + z + w;
                a[i | l] = y + (z - w) * I;
                a[i | m] = x - z - w;
                a[i | m | l] = y - (z - w) * I;
            }
        }

        constexpr void IDFT();

        public:

        constexpr POLY(auto... args) : vmi(args...) {}
        constexpr POLY(const std::initializer_list <mi>& init) : vmi(init) {}

        constexpr pl operator-() const
        {
            auto res = *this;
            for(auto& x : res) x = -x;
            return res;
        }
        constexpr pl diff() const
        {
            POLY f = *this;
            for(i32 i = 0; i + 1 < f.size(); i ++)
                f[i] = f[i + 1] * (i + 1);
            f.pop_back();
            return f;
        }
        constexpr pl inte() const
        {
            POLY f = *this;
            f.push_back(0);
            for(i32 i = f.size() - 1; i > 0; i --)
                f[i] = f[i - 1] / i;
            return f[0] = 0, f;
        }
        constexpr pl inv() const
        {
            i32 m = this->size();
            i32 n = m > 1 ? 1 << 32 - __builtin_clz(m - 1) : 1;
            POLY f = *this, g(1); f.resize(n), g[0] = 1 / f[0];
            for(i32 k = 2; k <= n; k <<= 1)
            {
                auto tmpg = g; tmpg.resize(k << 1), tmpg.DFT();
                auto tmpf = f; tmpf.resize(k), tmpf.resize(k << 1), tmpf.DFT();
                tmpf = tmpg * 2 - (tmpf | tmpg | tmpg);
                tmpf.IDFT(), tmpf.resize(k), g = tmpf;
            }
            return g.resize(m), g;
        }
        constexpr pl sqr() const
        {
            i32 m = this->size();
            i32 n = m > 1 ? 1 << 32 - __builtin_clz(m - 1) : 1;
            POLY f = *this, g(1); f.resize(n), g[0] = f[0].sqr();
            for(i32 k = 2; k <= n; k <<= 1)
            {
                g.resize(k);
                auto tmpf = f; tmpf.resize(k);
                g = (tmpf + g * g) / (g * 2);
            }
            return g.resize(m), g;
        }
        constexpr pl log() const
        {
            assert((*this)[0] == 1);
            POLY f = *this;
            f = f.diff() * f.inv();
            return f.inte();
        }
        constexpr pl exp() const
        {
            assert((*this)[0] == 0);
            i32 m = this->size();
            i32 n = m > 1 ? 1 << 32 - __builtin_clz(m - 1) : 1;
            POLY f = *this, g(1); f.resize(n), f[0] = g[0] = 1;
            for(i32 k = 2; k <= n; k <<= 1)
            {
                g.resize(k);
                auto tmpf = f; tmpf.resize(k);
                g = (tmpf - g.log()) * g;
            }
            return g.resize(m), g;
        }
        constexpr pl pow(const i32& k, const i32& k2 = -1) const
        {
            assert(k >= 0);
            i32 m = this->size();
            POLY f = *this; i32 shift = 0;
            while(shift < m && !f[shift].val()) ++shift;
            if(shift == m) return f;
            if(1ll * shift * k >= m) return f.assign(m, 0), f;
            mi tmp = 1 / f[shift];
            for(i32 i = shift; i < m; i ++) f[i - shift] = f[i] * tmp;
            f = (f.log() * k).exp();
            tmp = (1 / tmp).pow(k2 < 0 ? k : k2), shift *= k, f.resize(m + shift);
            for(i32 i = m + shift - 1; i >= shift; i --) f[i] = f[i - shift] * tmp;
            for(i32 i = shift - 1; i >= 0; i --) f[i] = 0;
            return f.resize(m), f;
        }

        constexpr pl& operator+=(const pl& rhs) {return (*this) = (*this) + rhs;}
        constexpr pl& operator-=(const pl& rhs) {return (*this) = (*this) - rhs;}
        constexpr pl& operator|=(const pl& rhs) {return (*this) = (*this) | rhs;} // inner product
        constexpr pl& operator*=(const pl& rhs) {return (*this) = (*this) * rhs;}
        constexpr pl& operator*=(const mi& rhs) {return (*this) = (*this) * rhs;}
        constexpr pl& operator*=(const i32& rhs) {return (*this) = (*this) * rhs;}
        constexpr pl& operator/=(const pl& rhs) {return (*this) = (*this) / rhs;}
        constexpr pl& operator%=(const pl& rhs) {return (*this) = (*this) % rhs;}

        constexpr friend pl operator+(const pl& lhs, const pl& rhs)
        {
            auto res = lhs;
            res.resize(std::max(lhs.size(), rhs.size()));
            for(i32 i = 0; i < rhs.size(); i ++) res[i] += rhs[i];
            return res;
        }
        constexpr friend pl operator-(const pl& lhs, const pl& rhs)
        {
            auto res = lhs;
            res.resize(std::max(lhs.size(), rhs.size()));
            for(i32 i = 0; i < rhs.size(); i ++) res[i] -= rhs[i];
            return res;
        }
        constexpr friend pl operator|(const pl& lhs, const pl& rhs) // inner product
        {
            auto res = lhs;
            res.resize(std::max(lhs.size(), rhs.size()));
            for(i32 i = 0; i < rhs.size(); i ++) res[i] *= rhs[i];
            return res;
        }
        constexpr friend pl operator*(const pl& lhs, const mi& rhs)
        {
            auto res = lhs;
            for(i32 i = 0; i < lhs.size(); i ++) res[i] *= rhs;
            return res;
        }
        constexpr friend pl operator*(const pl& lhs, const i32& rhs)
        {
            return lhs * mi(rhs);
        }
        constexpr friend pl operator*(const pl& lhs, const pl& rhs)
        {
            i32 m = lhs.size() + rhs.size() - 1;
            i32 n = m > 1 ? 1 << 32 - __builtin_clz(m - 1) : 1;
            auto f = lhs, g = rhs; f.resize(n), g.resize(n);
            f.DFT(), g.DFT(), f |= g, f.IDFT();
            return f.resize(m), f;
        }
        constexpr friend pl operator/(const pl& lhs, const pl& rhs)
        {
            return lhs * rhs.inv();
        }
        constexpr friend pl operator%(const pl& lhs, const pl& rhs)
        {
            i32 n = lhs.size(), m = rhs.size();
            if(m > n) return lhs; pl f = lhs, g = rhs;
            reverse(f.begin(), f.end()), f.resize(n - m + 1);
            reverse(g.begin(), g.end()), g.resize(n - m + 1);
            pl p = f / g; p.resize(n - m + 1);
            reverse(p.begin(), p.end()), p = lhs - rhs * p;
            return p.resize(m - 1), p;
        }
    };

    template <> void POLY::DIF<4>(const POLY::iterator& a)
    {
        mi x = a[0], y = a[1], z = a[2], w = a[3];
        a[0] = x + y + z + w;
        a[1] = x - y + z - w;
        a[2] = x - z + (y - w) * I;
        a[3] = x - z - (y - w) * I;
    }
    template <> void POLY::DIF<2>(const POLY::iterator& a)
    {
        mi x = a[0], y = a[1];
        a[0] = x + y, a[1] = x - y;
    }
    template <> void POLY::DIF<1>(const POLY::iterator& a) {}

    constexpr void POLY::DFT()
    {
        i32 n = this->size();
        switch(n)
        {
            case 1 <<  0 : DIF<1 <<  0>(this->begin()); break;
            case 1 <<  1 : DIF<1 <<  1>(this->begin()); break;
            case 1 <<  2 : DIF<1 <<  2>(this->begin()); break;
            case 1 <<  3 : DIF<1 <<  3>(this->begin()); break;
            case 1 <<  4 : DIF<1 <<  4>(this->begin()); break;
            case 1 <<  5 : DIF<1 <<  5>(this->begin()); break;
            case 1 <<  6 : DIF<1 <<  6>(this->begin()); break;
            case 1 <<  7 : DIF<1 <<  7>(this->begin()); break;
            case 1 <<  8 : DIF<1 <<  8>(this->begin()); break;
            case 1 <<  9 : DIF<1 <<  9>(this->begin()); break;
            case 1 << 10 : DIF<1 << 10>(this->begin()); break;
            case 1 << 11 : DIF<1 << 11>(this->begin()); break;
            case 1 << 12 : DIF<1 << 12>(this->begin()); break;
            case 1 << 13 : DIF<1 << 13>(this->begin()); break;
            case 1 << 14 : DIF<1 << 14>(this->begin()); break;
            case 1 << 15 : DIF<1 << 15>(this->begin()); break;
            case 1 << 16 : DIF<1 << 16>(this->begin()); break;
            case 1 << 17 : DIF<1 << 17>(this->begin()); break;
            case 1 << 18 : DIF<1 << 18>(this->begin()); break;
            case 1 << 19 : DIF<1 << 19>(this->begin()); break;
            case 1 << 20 : DIF<1 << 20>(this->begin()); break;
            case 1 << 21 : DIF<1 << 21>(this->begin()); break;
        }
    }

    template <> void POLY::DIT<4>(const POLY::iterator& a)
    {
        mi x = a[0], y = a[1], z = a[2], w = a[3];
        a[0] = x + y + z + w;
        a[1] = x - y + (z - w) * I;
        a[2] = x + y - z - w;
        a[3] = x - y - (z - w) * I;
    }
    template <> void POLY::DIT<2>(const POLY::iterator& a)
    {
        mi x = a[0], y = a[1];
        a[0] = x + y, a[1] = x - y;
    }
    template <> void POLY::DIT<1>(const POLY::iterator& a) {}

    constexpr void POLY::IDFT()
    {
        i32 n = this->size();
        switch(n)
        {
            case 1 <<  0 : DIT<1 <<  0>(this->begin()); break;
            case 1 <<  1 : DIT<1 <<  1>(this->begin()); break;
            case 1 <<  2 : DIT<1 <<  2>(this->begin()); break;
            case 1 <<  3 : DIT<1 <<  3>(this->begin()); break;
            case 1 <<  4 : DIT<1 <<  4>(this->begin()); break;
            case 1 <<  5 : DIT<1 <<  5>(this->begin()); break;
            case 1 <<  6 : DIT<1 <<  6>(this->begin()); break;
            case 1 <<  7 : DIT<1 <<  7>(this->begin()); break;
            case 1 <<  8 : DIT<1 <<  8>(this->begin()); break;
            case 1 <<  9 : DIT<1 <<  9>(this->begin()); break;
            case 1 << 10 : DIT<1 << 10>(this->begin()); break;
            case 1 << 11 : DIT<1 << 11>(this->begin()); break;
            case 1 << 12 : DIT<1 << 12>(this->begin()); break;
            case 1 << 13 : DIT<1 << 13>(this->begin()); break;
            case 1 << 14 : DIT<1 << 14>(this->begin()); break;
            case 1 << 15 : DIT<1 << 15>(this->begin()); break;
            case 1 << 16 : DIT<1 << 16>(this->begin()); break;
            case 1 << 17 : DIT<1 << 17>(this->begin()); break;
            case 1 << 18 : DIT<1 << 18>(this->begin()); break;
            case 1 << 19 : DIT<1 << 19>(this->begin()); break;
            case 1 << 20 : DIT<1 << 20>(this->begin()); break;
            case 1 << 21 : DIT<1 << 21>(this->begin()); break;
        }

        for(i32 i = 1; i < n >> 1; i ++)
            std::swap((*this)[i], (*this)[n - i]);
        mi inv = mi(n).pow(MOD - 2);
        for(auto& x : *this) x *= inv;
    }
}

using poly = polyNomial::POLY;

void staring::mainSolve()
{
    int n, m;
    read(n, m);
    poly f(n + 1), g(m + 1);
    for (int t; auto &x : f) read(t), x = t;
    for (int t; auto &x : g) read(t), x = t;
    f *= g;
    for (auto x : f) write(x.val(), ' ');
}

评测结果