文件详细信息

下载本文件

本文件的大小为 1511 字节。

#include<cstdio>
typedef long long ll;
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
void write(int a){
	if(a>=10)write(a/10);
	putchar(a%10|48);
}
const ll P=998244353;
const int maxn=1<<21|10;
ll qpow(ll a,int x=P-2){
	if(x==0)return 1%P;
	ll answer=1;
	while(x){
		if(x&1)answer=answer*a%P;
		a=a*a%P;
		x>>=1;
	}
	return answer;
}
inline void qmod(ll&x){
	x=x+((x>>63)&P);
}
const ll G=3,invG=qpow(G);
void ntt(ll*f,int len,bool type,ll*h){
	if(len==1)return;
	ll*fl=f,*fr=f+(len>>1);
	for(int k=0;k<len;k++)h[k]=f[k];
	for(int k=0;k<len>>1;k++)fl[k]=h[k<<1],fr[k]=h[k<<1|1];
	ntt(fl,len>>1,type,h),ntt(fr,len>>1,type,h);
	ll tG=qpow(type?G:invG,(P-1)/len),buf=1;
	for(int k=0;k<len>>1;k++){
	    ll tmp=buf*fr[k]%P;
		qmod(h[k]=fl[k]+tmp-P);
		qmod(h[k+(len>>1)]=fl[k]-tmp);
		buf=buf*tG%P;
	}
	for(int k=0;k<len;k++)f[k]=h[k];
}
void poly_mul(ll*f,ll*g,ll*h,int&n,int&m){
	ll nf[maxn],ng[maxn],nh[maxn];
	for(int i=0;i<=n;i++)nf[i]=f[i];
	for(int i=0;i<=m;i++)ng[i]=g[i];
	for(m+=n,n=1;n<=m;n<<=1);
	ntt(nf,n,true,nh),ntt(ng,n,true,nh);
	for(int i=0;i<n;i++)nf[i]=nf[i]*ng[i]%P;
	ntt(nf,n,false,nh);
	ll invn=qpow(n);
	for(int i=0;i<n;i++)h[i]=((nf[i]*invn%P+P)%P);
}
int n,m;
ll a[maxn],b[maxn],c[maxn];
int main(){
	n=read(),m=read();
	for(int i=0;i<=n;i++)a[i]=read();
	for(int i=0;i<=m;i++)b[i]=read();
	poly_mul(a,b,c,n,m);
	for(int i=0;i<=m;i++)write(c[i]),putchar(i!=m?' ':'\n');
	return 0;
}