代码

#include <algorithm>
#include <vector>
#include <cstdio>
#include <string.h>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll Q = 998244353, G = 3;
const int MaxN = 6e5 + 7;
ll qpow(ll a,int n)
{
    ll bas = 1;
    while (n)
    {
        if (n & 1)
            (bas *= a) %= Q;
        (a *= a) %= Q, n >>= 1;
    }
    return bas;
}
ll inv(ll a) { return qpow(a, Q - 2); }
const ll ivG = inv(G);
int tr[MaxN];
inline void tpre(int len)
{
    for(int i = 1; i < len; ++i)
    {
        tr[i] = tr[i >> 1] >> 1;
        if (i & 1)
            tr[i] |= len >> 1;
    }
}
template<class Tp>
inline void clr(Tp *f, int len) { memset(f, 0, sizeof(Tp) * len); }
template<class Tp>
inline void cpy(Tp *f, Tp *g, int len) { memcpy(f, g, sizeof(Tp) * len); }
void NTT(int *f, bool tp, int len)
{
    static ull t1[MaxN], t2[MaxN];
    t2[0] = 1;
    tpre(len);
    for (int i = 0; i < len; ++i)
        t1[i] = f[tr[i]];
    for (int i = 1; i < len; i <<= 1)
    {
        ull wn = qpow(tp ? G : ivG, (Q - 1) / (i + i));
        for (int j = 1; j < i; ++j)
            t2[j] = t2[j - 1] * wn % Q;
        for (int j = 0; j < len; j += i)
            for (int k = 0; k < i; ++k)
            {
                ull t = t1[i | j | k] * t2[k] % Q;
                t1[i | j | k] = t1[j | k] + Q - t;
                t1[j | k] += t;
            }
        if (i == (1 << 10))
            for (int j = 0; j < len; ++j)
                t1[j] %= Q;
    }
    if (tp)
        for (int i = 0; i < len; ++i)
            f[i] = t1[i] % Q;
    else
    {
        ull ivl = inv(len);
        for (int i = 0; i < len; ++i)
            f[i] = t1[i] % Q * ivl % Q;
    }
}
void vmul(int *f, int *g, int len)
{
    for (int i = 0; i < len; ++i)
        f[i] = 1ll * f[i] * g[i] % Q;
}
void times(int *f, int *g, int m1, int m2)
{
    int len = 1 << (32 - __builtin_clz(m1 + m2 - 2));
    clr(f + m1, len - m1), clr(g + m2, len - m2);
    NTT(f, 1, len), NTT(g, 1, len);
    vmul(f, g, len);
    NTT(f, 0, len), NTT(g, 0, len);
}
void inver(int *h, int *f, int len)
{
    int n = 1;
    f[0] = inv(h[0]);
    static int w1[MaxN], w2[MaxN];
    while (n < len)
    {
        clr(f + n, n);
        cpy(w1, h, n + n);
        cpy(w2, f, n), clr(w2 + n, n);
        NTT(w1, 1, n + n), NTT(w2, 1, n + n);
        vmul(w1, w2, n + n);
        NTT(w1, 0, n + n), clr(w1, n);
        NTT(w1, 1, n + n), vmul(w1, w2, n + n);
        NTT(w1, 0, n + n);
        for (int i = n; i < n + n; ++i)
            f[i] = (Q - w1[i]) % Q;
        n <<= 1;
    }
    clr(f + len, n - len);
}
void ints(int *f, int len)
{
    for (int i = len + 1; i; --i)
        f[i] = 1ll * f[i - 1] * inv(i) % Q;
    f[0] = 0;
}
void wers(int *f, int len)
{
    for (int i = 0; i < len - 1; ++i)
        f[i] = 1ll * f[i + 1] * (i + 1) % Q;
    f[len] = 0;
}
void lnp(int *f, int *g, int len)
{
    static int w1[MaxN], w2[MaxN];
    cpy(w1, f, len), wers(w1, len);
    inver(f, w2, len);
    times(w1, w2, len, len);
    ints(w1, len);
    cpy(g, w1, len);
}
void pexp(int *h, int *f, int len)
{
    int n = 2;
    f[0] = 1;
    static int w1[MaxN], w2[MaxN];
    while (n < len + len)
    {
        clr(f + (n >> 1), n + (n >> 1));
        lnp(f, w1, n), clr(w1 + n, n);
        cpy(w2, h, n), clr(w2 + n, n);
        NTT(f, 1, n + n), NTT(w1, 1, n + n), NTT(w2, 1, n + n);
        for (int i = 0; i < n + n; ++i)
            f[i] = 1ll * (1 + Q - w1[i] + w2[i]) % Q * f[i] % Q;
        NTT(f, 0, n + n);
        clr(f + n, n);
        n <<= 1;
    }
    clr(f + len, n - len);
}
void powp(int *h, int *f, int k, int len)
{
    static int w[MaxN];
    lnp(h, w, len);
    for (int i = 0; i < len; ++i)
        w[i] = 1ll * w[i] * k % Q;
    pexp(w, f, len);
}
ll si;
struct Complex
{
    ll a, b;
    Complex operator*(const Complex x) const { return (Complex){(a * x.a + b * x.b % Q * si) % Q, (a * x.b + b * x.a) % Q}; }
};
mt19937_64 my_rand(11451467);
Complex qpow(Complex a, int n)
{
    Complex bas{1, 0};
    while (n)
    {
        if (n & 1)
            bas = bas * a;
        a = a * a, n >>= 1;
    }
    return bas;
}
ll sq(ll n)
{
    ll x;
    while (1)
    {
        x = my_rand() % Q;
        if (qpow((x * x + Q - n) % Q, (Q - 1) / 2) == Q - 1)
            break;
    }
    si = (x * x + Q - n) % Q;
    Complex a(qpow((Complex){x, 1}, (Q + 1) / 2));
    return min(a.a, (Q - a.a) % Q);
}
void sqrtp(int *h, int *f, int len)
{
    int n = 2;
    static int w1[MaxN], w2[MaxN];
    f[0] = sq(h[0]);
    ll iv2 = inv(2);
    while (n < len + len)
    {
        clr(f + (n >> 1), n >> 1);
        cpy(w1, h, n), clr(w1 + n, n);
        inver(f, w2, n), clr(w2 + n, n);
        NTT(f, 1, n + n), NTT(w1, 1, n + n), NTT(w2, 1, n + n);
        for (int i = 0; i < n + n; ++i)
            f[i] = 1ll * (1ll * f[i] * f[i] % Q + w1[i]) % Q * w2[i] % Q * iv2 % Q;
        NTT(f, 0, n + n);
        clr(f + n, n);
        n <<= 1;
    }
    clr(f + len, n - len);
}
int f[MaxN], g[MaxN];
int main()
{
    int n, m, i;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; ++i) scanf("%d", f+i);
    for (i = 0; i < m; ++i) scanf("%d", g+i);
    times(f, g, n, m);
    for (i = 0; i < n+m-1; ++i)
        printf("%d ", f[i]);
    return 0;
}

评测结果