代码

#include <algorithm>
#include <vector>
#include <cstdio>
#include <string.h>
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];
ull t1[MaxN], t2[MaxN], t3[MaxN];
inline void tpre(int len)
{
    int lg = __lg(len);
    for(int i = 1; i < len; ++i)
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (lg - 1));
}
template<class Tp>
inline void clear(Tp *f, int len) { memset(f, 0, sizeof(Tp) * len); }
void NTT(int *f,bool tp,int len)
{
    tpre(len);
    t2[0] = 1;
    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 (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;
    }
    clear(t1, len), clear(t2, len);
}
int f[MaxN], g[MaxN];
int main()
{
    int m1, m2, i;
    scanf("%d%d", &m1, &m2),++m1,++m2;
    for (i = 0; i < m1; ++i)
        scanf("%d", f + i);
    for (i = 0; i < m2; ++i)
        scanf("%d", g + i);
    int len = 1;
    while (len < m1 + m2 - 1)
        len <<= 1;
    NTT(f, 1, len), NTT(g, 1, len);
    for (i = 0; i < len; ++i)
        f[i] = 1ll * f[i] * g[i] % Q;
    NTT(f, 0, len);
    for (i = 0; i < m1 + m2 - 1; ++i)
        printf("%d%c", f[i], " \n"[i == m1 + m2 - 2]);
    return 0;
}

评测结果