代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=262145,M=998244353;
inline void reduce(int&x){x+=x>>31&M;}
int len,a[N],n,m,b[N],rev[N],w[N<<1];
inline int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(ull)x*x%M)
		if (y&1)ans=(ull)ans*x%M;
	return ans;
}
inline void init(){
	for (int i=1;i<len;i++)rev[i]=rev[i>>1]>>1|((i&1)*len/2);
}
inline void ntt(int y[],int opt){
	for (int i=1;i<len;i++)
		if (rev[i]>i)swap(y[i],y[rev[i]]);
	for (int h=1;h<len;h<<=1)
		for (int j=0;j<len;j+=h+h)
			for(int k=0;k<h;++k){
				const int x = (ull) y[h + j + k] * w[h + k] % M;
				reduce(y[h + j + k] = y[j + k] - x);
				reduce(y[j + k] += x - M);
			}
	if (opt==-1){
		int temp=ksm(len,M-2);
		for (int i=0;i<len;i++)y[i]=(ull)y[i]*temp%M;
		reverse(y+1,y+len);
	}
}
namespace IO {
	char rbuf[(int) 1.5e7], *in = rbuf, wbuf[(int) 8e6], *out = wbuf, ch;
	inline void init() { std::fread(rbuf, 1, 1.5e7, stdin); }
	inline char getchar() { return *in++; }
	inline void read(int &x) {
		bool f = 0;
		while (std::isspace(ch = getchar()));
		if (ch == '-') f = 1, ch = getchar(); x = ch & 15;
		while (std::isdigit(ch = getchar())) x = x * 10 + (ch & 15);
		if (f) x = -x;
	}
	inline void putchar(char ch) { *out++ = ch; }
	inline void write(int x) {
		if (x > 9) write(x / 10);
		putchar(x % 10 + 48);
	}
	inline void end() { std::fwrite(wbuf, 1, out - wbuf, stdout); }
};
int main(){
	IO::init();
	IO::read(n);IO::read(m);
	n++;m++;
	for (int i=0;i<n;i++)IO::read(a[i]);
	for (int i=0;i<m;i++)IO::read(b[i]);
	n+=m;n--;len=1;
	while (len<n)len<<=1;
	for(int mid = 1;mid < len;mid <<= 1) {
		const int wn = ksm(3,M / mid / 2); w[mid] = 1;
		for(int i = 1;i < mid;++i) w[i + mid] = (ull) w[i + mid - 1] * wn % M;
	}
	init();
	ntt(a,1);
	ntt(b,1);
	for (int i=0;i<len;i++)a[i]=(ull)a[i]*b[i]%M;
	ntt(a,-1);
	for (int i=0;i<n;i++)IO::write(a[i]),IO::putchar(' ');
	IO::end();
}

评测结果