代码

#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#pragma GCC optimize("-fno-math-errno")
#pragma GCC optimize("-funsafe-math-optimizations")
#pragma GCC optimize("-freciprocal-math")
#pragma GCC optimize("-fno-trapping-math")
#pragma GCC optimize("-ffinite-math-only")
#pragma GCC optimize("-fno-stack-protector")
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2345678
const int MOD=998244353;
ll qp(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return ans;
}
int getK(int n)
{int s=1; while(s<n) s<<=1; return s;}
typedef unsigned us;
typedef unsigned long long ull;
us pool[SZ*4] __attribute__ ((aligned(64))),*ptr=pool;
us *p0[SZ],*p1[SZ],*q0[SZ],*q1[SZ];
__attribute__((always_inline)) void bit_flip(us*p,int t)
{
	for(int i=0,j=0;i<t;++i)
	{
		if(i>j) swap(p[i],p[j]);
		for(int l=t>>1;(j^=l)<l;l>>=1);
	}
}
void prep(int n)
{
	static int t=1;
	for(;t<n;t<<=1)
	{
		int g=qp(3,(MOD-1)/(t*2));
		us*p,*q;
		p=p0[t]=ptr; ptr+=max(t,16); p[0]=1;
		for(int m=1;m<t;++m)
			p[m]=p[m-1]*(ull)g%us(MOD);
		bit_flip(p,t);
		q=q0[t]=ptr; ptr+=max(t,16);
		for(int i=0;i<t;++i)
			q[i]=(ull(p[i])<<32)/MOD;
		g=qp(g,MOD-2);
		p=p1[t]=ptr; ptr+=max(t,16); p[0]=1;
		for(int m=1;m<t;++m)
			p[m]=p[m-1]*(ull)g%us(MOD);
		bit_flip(p,t);
		q=q1[t]=ptr; ptr+=max(t,16);
		for(int i=0;i<t;++i)
			q[i]=(ull(p[i])<<32)/MOD;
	}
}
typedef unsigned long long ull;
__attribute__((always_inline)) us my_mul(us a,us b,us c)
{
	return b*(ull)a-((ull(a)*c)>>32)*ull(998244353);
}
void ntt(us* x,int n,bool f=true)
{
	prep(n); int t=n;
	for(int m=1;m<n;m<<=1)
	{
		t>>=1;
		us* p=p0[m];
		us* q=q0[m];
		us *xa=x,*xb=x+t;
		for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)
			for(int j=0;j<t;++j)
			{
				us u=xa[j]-(xa[j]>=us(MOD+MOD))*us(MOD+MOD);
				us v=my_mul(xb[j],p[i],q[i]);
				xa[j]=u+v;
				xb[j]=u-v+us(MOD+MOD);
			}
	}
	for(int i=0;i<n;++i)
		x[i]-=(x[i]>=us(MOD+MOD))*us(MOD+MOD),
		x[i]-=(x[i]>=us(MOD))*us(MOD);
	if(f) bit_flip(x,n);
}
void intt(us* x,int n,bool f=true)
{
	prep(n); int t=1;
	if(f) bit_flip(x,n);
	for(int m=(n>>1);m;m>>=1)
	{
		us* p=p1[m];
		us* q=q1[m];
		us *xa=x,*xb=x+t;
		for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)
			for(int j=0;j<t;++j)
			{
				us u=xa[j],v=xb[j];
				xa[j]=u+v-(u+v>=us(MOD+MOD))*us(MOD+MOD);
				xb[j]=my_mul(u-v+us(MOD+MOD),p[i],q[i]);
			}
		t<<=1;
	}
	us rn=qp(n,MOD-2);
	for(int i=0;i<n;++i)
		x[i]=x[i]*(ull)rn%MOD;
}
//modint wrapper
struct mi
{
us w;
mi() {}
mi(us u) {w=u;}
mi(int u) {u%=MOD; w=u+((u<0)?MOD:0);}
explicit operator us() {return w;}
explicit operator int() {return w;}
};
mi operator + (const mi& a,const mi& b)
{return mi{a.w+b.w-((a.w+b.w>=MOD)?(MOD):0)};}
mi operator - (const mi& a,const mi& b)
{return mi{a.w-b.w+((a.w<b.w)?(MOD):0)};}
mi operator * (const mi& a,const mi& b)
{return mi{us((ull)a.w*b.w%MOD)};}
mi operator / (const mi& a,const mi& b)
{return mi{us((ull)a.w*qp(b.w,MOD-2)%MOD)};}
mi inv(const mi& a)
{return mi{us(qp(a.w,MOD-2))};}
//what could possibly go wrong?
void ntt(mi* x,int n,bool f=true) {ntt((us*)x,n,f);}
void intt(mi* x,int n,bool f=true) {intt((us*)x,n,f);}
//copied from http://uoj.ac/submission/386710
typedef unsigned uint;
struct IO_Tp
{
	const static int _I_Buffer_Size = 2 << 20;
	char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;
	
	const static int _O_Buffer_Size = 2 << 20;
	char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
	
	uint m[10000];
	
	IO_Tp()
	{
		constexpr uint e0 = '\0\0\0\1', e1 = '\0\0\1\0', e2 = '\0\1\0\0', e3 = '\1\0\0\0';
		int x = 0;
		for (uint i = 0, c0 = '0000'; i != 10; ++i, c0 += e0)
			for (uint j = 0, c1 = c0; j != 10; ++j, c1 += e1)
				for (uint k = 0, c2 = c1; k != 10; ++k, c2 += e2)
					for (uint l = 0, c3 = c2; l != 10; ++l, c3 += e3)
						m[x++] = c3;
		
		fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
	}
	~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
	
	IO_Tp &operator>>(int &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ - '0';
		while (isdigit(*_I_pos))
			res = res * 10 + (*_I_pos++ - '0');
		return *this;
	}
	
	IO_Tp &operator>>(mi &res_)
	{
		uint res=0;
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ - '0';
		while (isdigit(*_I_pos))
			res = res * 10 + (*_I_pos++ - '0');
		(res>=MOD+MOD)?(res-=MOD+MOD):0;
		(res>=MOD)?(res-=MOD):0;
		res_.w=res;
		return *this;
	}
	
	IO_Tp &operator>>(uint &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ - '0';
		while (isdigit(*_I_pos))
			res = res * 10 + (*_I_pos++ - '0');
		return *this;
	}
	
	IO_Tp &operator<<(mi x_)
	{
		us x=x_.w;
		if (x == 0)
		{
			*_O_pos++ = '0';
			return *this; 
		}
		static char _buf[12];
		char *_pos = _buf + 12;
		if (x >= 10000)
			*--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
		if (x >= 10000)
			*--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
		*--reinterpret_cast<uint *&>(_pos) = m[x];
		_pos += (x < 1000) + (x < 100) + (x < 10);
		_O_pos = std::copy(_pos, _buf + 12, _O_pos);
		return *this;
	}
	
	IO_Tp &operator<<(uint x)
	{
		if (x == 0)
		{
			*_O_pos++ = '0';
			return *this; 
		}
		static char _buf[12];
		char *_pos = _buf + 12;
		if (x >= 10000)
			*--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
		if (x >= 10000)
			*--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
		*--reinterpret_cast<uint *&>(_pos) = m[x];
		_pos += (x < 1000) + (x < 100) + (x < 10);
		_O_pos = std::copy(_pos, _buf + 12, _O_pos);
		return *this;
	}
	
	IO_Tp &operator<<(char ch)
	{
		*_O_pos++ = ch;
		return *this;
	}
} IO;
int N,M;
mi a[2345678] __attribute__ ((aligned(64)));
mi b[2345678] __attribute__ ((aligned(64)));
int main()
{
	IO>>N; IO>>M; ++N; ++M; int t=N+M-1;
	for(int i=0;i<N;i++) IO>>a[i];
	for(int i=0;i<M;i++) IO>>b[i];
	int K=getK(t); prep(K);
	ntt(a,K,0); ntt(b,K,0);
	for(int i=0;i<K;i++) a[i]=a[i]*b[i];
	intt(a,K,0); for(int i=0;i<t;i++) IO<<a[i]<<' ';
}

评测结果