代码

#include <bit>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define For(i,a,b) for (int i = (a), i##__end = (b); i <= i##__end; ++i)
#define Ford(i,a,b) for (int i = (a), i##__end = (b); i >= i##__end; --i)
#define Rg(i,a,b) for (int i = int(a), i##__end = int(b); i < i##__end; ++i)
#define Rgd(i,a,b) for (int i = int(a) - 1, i##__end = int(b); i >= i##__end; --i)
using u32 = unsigned int;
using ull = unsigned long long;
using ll = long long;
using lf = long double;
using lll = __int128_t;
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using piii = tuple<int, int, int>;
using piil = tuple<int, int, ll>;
#define fi first
#define se second
#define dmp(x) cout << #x << " : " << endl;
#define fn(name, ...) auto name = [&](auto && name __VA_OPT__(,) __VA_ARGS__)

namespace Fastio {
	#define USE_FASTIO 1
	#define IN_LEN 450000
	#define OUT_LEN 450000
	char ch, c; int len;
	short f, top, s;
	inline char Getchar() {
		static char buf[IN_LEN], *l = buf, *r = buf;
		if (l == r) r = (l = buf) + fread(buf, 1, IN_LEN, stdin);
		return (l == r) ? EOF : *l++;
	}
	char obuf[OUT_LEN], *ooh = obuf;
	inline void Putchar(char c) {
		if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
		*ooh++ = c;
	}
	inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

	#undef IN_LEN
	#undef OUT_LEN
	struct Reader {
		template <typename T> Reader& operator >> (T &x) {
			x = 0, f = 1, c = Getchar();
			while (!isdigit(c)) { if (c == '-') f *= -1; c = Getchar(); }
			while ( isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = Getchar();
			x *= f;
			return *this;
		}
		
		Reader() {}
	} cin;
	const char endl = '\n';
	struct Writer {
		typedef long long mxdouble;
		template <typename T> Writer& operator << (T x) {
			if (x == 0) { Putchar('0'); return *this; }
			if (x < 0) Putchar('-'), x = -x;
			static short sta[40];
			top = 0;
			while (x > 0) sta[++top] = x % 10, x /= 10;
			while (top > 0) Putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (const char *str) {
			int cur = 0;
			while (str[cur]) Putchar(str[cur++]);
			return *this;
		}
		inline Writer& operator << (char c) {Putchar(c); return *this;}
		Writer() {}
		~ Writer () {flush();}
	} cout;
	#define cin Fastio::cin
	#define cout Fastio::cout
	#define endl Fastio::endl
}

template<class T>
T qpow(T x, ll y) {
    T r = 1;
    for (; y; x *= x, y >>= 1) if (y & 1) r *= x;
    return r;
}

// template<int & _mod>
// struct ZZ {
//     constexpr static int const & mod = _mod;
//     int x;
//     int norm(ll x) { return (x % mod + mod) % mod; }
//     ZZ() : x(0) {}
//     ZZ(int x) : x(norm(x)) {}
//     ZZ(ll x) : x(norm(x)) {}
//     int val() const { return x; }
//     ZZ operator-() const { return ZZ(x ? mod - x : 0);}
//     ZZ inv() const { assert(x); return qpow(*this, mod - 2); }
//     ZZ &operator*=(const ZZ &r) { x = 1ll * x * r.x % mod; return *this; }
//     ZZ &operator+=(const ZZ &r) { x += r.x; if (x >= mod) x -= mod; return *this; }
//     ZZ &operator-=(const ZZ &r) { x -= r.x; if (x < 0) x += mod; return *this; }
//     ZZ &operator/=(const ZZ &r) { return *this *= r.inv(); }
//     #define binop(op, bop) friend ZZ operator op (const ZZ &a, const ZZ &b) { ZZ r = a; r bop b; return r; }
//     binop(+, +=);
//     binop(*, *=);
//     binop(-, -=);
//     binop(/, /=);
//     #undef binop
//     friend istream &operator>>(istream &is, ZZ &a) {
//         ll v;
//         is >> v;
//         a = v;
//         return is;
//     }
//     friend ostream &operator<<(ostream &os, const ZZ &a) {
//         return os << a.val();
//     }
// };

template<const int _mod>
struct ZZ {
    constexpr static int mod = _mod;

    int x;
    int norm(ll x) { return (x % mod + mod) % mod; }
    ZZ() : x(0) {}
    ZZ(int x) : x(norm(x)) {}
    ZZ(ll x) : x(norm(x)) {}
    int val() const { return x; }
    ZZ operator-() const { return ZZ(x ? mod - x : 0);}
    ZZ inv() const { assert(x); return qpow(*this, mod - 2); }
    ZZ &operator*=(const ZZ &r) { x = (ull) x * r.x % mod; return *this; }
    ZZ &operator+=(const ZZ &r) { x += r.x; if (x >= mod) x -= mod; return *this; }
    ZZ &operator-=(const ZZ &r) { x -= r.x; if (x < 0) x += mod; return *this; }
    ZZ &operator/=(const ZZ &r) { return *this *= r.inv(); }
    #define binop(op, bop) friend ZZ operator op (const ZZ &a, const ZZ &b) { ZZ r = a; r bop b; return r; }
    binop(+, +=);
    binop(*, *=);
    binop(-, -=);
    binop(/, /=);
    #undef binop
    friend istream &operator>>(istream &is, ZZ &a) {
        ll v;
        is >> v;
        a = v;
        return is;
    }
    friend ostream &operator<<(ostream &os, const ZZ &a) {
        return os << a.val();
    }
};

template<class T>
struct frac {
    T a, b;
    void norm() {
        T g = gcd(a, b);
        a /= g, b /= g;
    }
    frac(T _a, T _b) : a(_a), b(_b) { if (b < 0) a = -a, b = -b; }
    frac() : frac(0, 1) {}
    frac(T n) : frac(n, 1) {}
    explicit operator double() const {
        return 1. * a / b;
    }
    frac &operator-() {
        return frac(-a, b);
    }
    frac &operator+=(const frac &r) {
        a = a * r.b + r.a * b;
        b *= r.b;
        return *this;
    }
    frac &operator-=(const frac &r) {
        a = a * r.b - r.a * b;
        b *= r.b;
        return *this;
    }
    frac &operator*=(const frac &r) {
        a *= r.a;
        b *= r.b;
        return *this;
    }
    frac &operator/=(const frac &r) {
        assert(r.a);
        a *= r.b;
        b *= r.a;
        if (b < 0) a = -a, b = -b;
        return *this;
    }
    #define binop(op, bop) friend frac operator op (const frac &a, const frac &b) { frac r = a; r bop b; return r; }
    binop(+, +=);
    binop(*, *=);
    binop(-, -=);
    binop(/, /=);
    #undef binop
    friend bool operator==(const frac &x, const frac &y) {
        return x.a * y.b == x.b * y.a;
    }
    friend bool operator!=(const frac &x, const frac &y) {
        return x.a * y.b != x.b * y.a;
    }
    friend bool operator<=(const frac &x, const frac &y) {
        return x.a * y.b <= x.b * y.a;
    }
    friend bool operator>=(const frac &x, const frac &y) {
        return x.a * y.b >= x.b * y.a;
    }
    friend bool operator<(const frac &x, const frac &y) {
        return x.a * y.b < x.b * y.a;
    }
    friend bool operator>(const frac &x, const frac &y) {
        return x.a * y.b > x.b * y.a;
    }
    friend ostream& operator<<(ostream &os, frac x) {
        x.norm();
        if (x.b == 1) return os << x.a;
        else return os << x.a << '/' << x.b;
    }
};

const int mod = 998244353;
using Z = ZZ<mod>;

int _sz = 1;
vector<Z> rt = {1};

template<bool rev = 0>
void dft(vector<Z> &a) {
    int n = a.size();

    while (_sz < n) {
        rt.resize(n);
        Z wn = qpow(Z(3), mod / 4 / _sz);
        Rg (i, 0, _sz) {
            rt[_sz + i] = rt[i] * wn;
        }
        _sz <<= 1;
    }

    auto calc = [&](int l) {
        for (auto i = a.begin(), ww = rt.begin(); i != a.end(); i += l << 1, ++ww) 
            for (auto uu = i, vv = i + l; uu != i + l; ++uu, ++vv) {
                auto &u = *uu, &v = *vv, &w = *ww;
                tie(u, v) = rev ? pair{u + v, (u - v) * w} : pair{u + v * w, u - v * w};
            } 
    };

    if (!rev) {
        for (int l = n >> 1; l >= 1; l >>= 1) calc(l);
    } else {
        for (int l = 1; l <= n >> 1; l <<= 1) calc(l);
        reverse(a.begin() + 1, a.end());
        auto iv = mod - (mod - 1) / n;
        for (auto &ai : a) ai *= iv;
    }
}

auto idft = dft<1>;

struct poly : vector<Z> {
    using vector<Z>::vector;
    poly &operator*=(poly g) {
        int len = size() + g.size() + 1;
        int sz = 1 << (__lg(len) + 1);
        // int sz = bit_ceil((uint)len);
        resize(sz), g.resize(sz);
        dft(*this), dft(g);
        Rg (i, 0, sz) (*this)[i] *= g[i];
        idft(*this);
        resize(len);
        return *this;
    }
};

void poly_multiply(unsigned *a, int n, unsigned * b, int m, unsigned *c) {
    poly f(n + 1), g(m + 1);
    Rg (i, 0, n + 1) f[i].x = a[i];
    Rg (i, 0, m + 1) g[i].x = b[i];

    f *= g;

    Rg (i, 0, n + m + 1) {
        c[i] = f[i].val();
    }
}

// const int N = 2e6 + 7;

// unsigned a[N], b[N], c[N];
// int main() {
//     int n, m;
//     cin >> n >> m;

//     For (i, 0, n) cin >> a[i];
//     For (i, 0, m) cin >> b[i];

//     poly_multiply(a, n, b, m, c);

//     For (i, 0, n + m) {
//         cout << c[i] << ' ';
//     }
// }

评测结果