代码

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; --i)
#define debug(x) cout << #x << " = " << x << endl
#define FIO(x) \
	freopen(x ".in", "r", stdin); \
	freopen(x ".out", "w", stdout);

#define swap(x,y) (x^=y,y^=x,x^=y)
#define mul(x,y) (1ll*x*y%P)
#define add(x,y) (x+y>=P?x+y-P:x+y)
#define dec(x,y) (x-y<0?x-y+P:x-y)

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

const int N = 4e5+10, P = 998244353;

int r[N], O[N];

inline int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=mul(res,a);
        a=mul(a,a),b>>=1;
    }
    return res;
}

void NTT(int *A,int type,int len){
    int limit=1,l=0;
    while(limit<len) limit<<=1,++l;
    for(int i=0;i<limit;++i)
    r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<limit;++i)
    if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1;mid<limit;mid<<=1){
        int R=mid<<1,Wn=ksm(3,(P-1)/R);O[0]=1;
        for(int j=1;j<mid;++j) O[j]=mul(O[j-1],Wn);
        for(int j=0;j<limit;j+=R){
            for(int k=0;k<mid;++k){
                int x=A[j+k],y=mul(O[k],A[j+k+mid]);
                A[j+k]=add(x,y),A[j+k+mid]=dec(x,y);
            }
        }
    }
    if(type==-1){
        reverse(A+1,A+limit);
        for(int i=0,invl=ksm(limit,P-2);i<limit;++i)
        A[i]=mul(A[i],invl);
    }
}

int a[N], b[N], n, m;

signed main() {
#ifndef ONLINE_JUDGE
	FIO("a");
#endif
	scanf("%d%d", &n, &m);
	FOR(i,0,n+1) scanf("%d", a+i);
	FOR(i,0,m+1) scanf("%d", b+i);
	int len = 1;
	while (len <= n+m+1) len <<= 1;
	NTT(a,1,len);
	NTT(b,1,len);
	FOR(i,0,len) a[i]=mul(a[i],b[i]);
	NTT(a,-1,len);
	FOR(i,0,n+m+1) printf("%d ", a[i]);
}

评测结果