代码

#ifndef fio
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#endif
#include<bits/stdc++.h>
using namespace std;

const int maxn=1<<21,mod=998244353;
using u32=uint32_t;using u64=uint64_t;using u128=unsigned __int128;
struct Montgomery{
	u32 m,ir;u64 lir;
	static constexpr u32 inv_m(u32 m){
		u32 x=1;
		for(int i=5;i--;)x*=2-x*m;
		return x;
	}
	constexpr Montgomery(u32 m_=2):m(m_),ir(-inv_m(m)),lir(((u128(1)<<96)+m-1)/m){}
	u32 tran(u32 a)const{return a*lir*u128(m)>>64;}
	u32 val(u32 a)const{return redc_m(redc(a)-m);}
	u32 add(u32 a, u32 b)const{return redc_m2(a+b-m*2);}
	u32 sub(u32 a, u32 b)const{return redc_m2(a-b);}
	u32 redc_m(u32 a)const{return a>>31?a+m:a;}
	u32 redc_m2(u32 a)const{return a>>31?a+m*2:a;}
	u32 redc(u64 a)const{return(a+u64(u32(a)*ir)*m)>>32;}
	u32 mul(u32 a,u32 b)const{return redc(u64(a)*b);}
}const mtg(998244353);
struct mint{
	u32 z;
	mint()=default;
	mint(int x):z(mtg.tran(x)){}
	mint(initializer_list<uint32_t>z):z(*z.begin()){}
	u32 val()const{return mtg.val(z);}
	#define mkopt_mint(star,mul)\
	mint operator star(mint const rhs)const{return{mtg.mul(z,rhs.z)};}\
	mint&operator star##=(mint const rhs){z=mtg.mul(z,rhs.z);return*this;}
	mkopt_mint(+,add)mkopt_mint(-,sub)mkopt_mint(*,mul)
};
inline mint qpow(mint a,int n){mint x=1;for(;n;a=a*a,n>>=1)if(n&1)x=x*a;return x;}

mint ntt_sup[maxn];
// void NTT(mint a[], int n, const int g=3) {
// 	auto ntt_a=ntt_sup,j=a,_j=a,k=ntt_a,_k=k,__k=k;int i;mint w,_w;
// 	for(i=1,w=qpow(g,(mod-1)/n);i<n;i<<=1,w=w*w,swap(a,ntt_a))
// 		for(k=ntt_a,j=a,_j=a+(n>>1),_w=1;k!=ntt_a+n;k+=i,_w=_w*w)
// 			for(_k=k,__k=(k+=i);_k!=k;++j,++_j,++_k,++__k)
// 				*_k=*j+*_j,
// 				*__k=(*j-*_j)*_w;
// 	if(ntt_a!=ntt_sup)memcpy(ntt_a,a,n*sizeof a[0]);
// }
void NTT(mint a[], int n, const int g=3){
	auto ntt_a=ntt_sup,j=a,_j=a;int i,k,_k;mint w,_w;
	for(i=1,w=qpow(g,(mod-1)/n);i<n;i<<=1,w=w*w,swap(a,ntt_a))
		for(k=0,j=a,_j=a+(n>>1),_w=1;k!=n;k+=i,_w=_w*w)
			for(_k=k,k+=i;_k!=k;++j,++_j,++_k)
				ntt_a[_k]=*j+*_j,
				ntt_a[_k+i]=(*j-*_j)*_w;
	if(ntt_a!=ntt_sup)memcpy(ntt_a,a,n*sizeof a[0]);
}
void INTT(mint a[],int n){NTT(a,n,(mod+1)/3);mint ivn=qpow(n,mod-2);for(int i=0;i<n;++i)a[i]=a[i]*ivn;}

mint A[maxn],B[maxn];

// signed main(){
// 	ios::sync_with_stdio(0),cin.tie(0);
// 	int n,m;cin>>n>>m;
// 	++n,++m;
// 	for(int i=0,z;i<n;++i)cin>>z,A[i]=z;
// 	for(int i=0,z;i<m;++i)cin>>z,B[i]=z;
// 	m=n+m-1;n=2<<__lg(m-1);
// 	NTT(A,n),NTT(B,n);
// 	for(int i=0;i<n;++i)A[i]*=B[i];
// 	INTT(A,n);
// 	for(int i=0;i<m;++i)cout<<A[i].val()<<' ';
// }

void poly_multiply(uint32_t*a,int n,uint32_t*b,int m,uint32_t*c){
	++n,++m;
	static mint A[maxn],B[maxn];
	for(int i=0;i<n;++i)A[i]=a[i];
	for(int i=0;i<m;++i)B[i]=b[i];
	n=2<<__lg((m=n+m-1)-1);
	NTT(A,n),NTT(B,n);
	for(int i=0;i<n;++i)A[i]*=B[i];
	INTT(A,n);
	for(int i=0;i<m;++i)c[i]=A[i].val();
}

评测结果