文件详细信息

下载本文件

本文件的大小为 1422 字节。

#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);
}
void swap(ll&a,ll&b){
	ll temp=a;
	a=b;
	b=temp;
}
const int maxn=1<<21;
const ll P=998244353;
ll qpow(ll a,int x=P-2){
	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);
int n,m;
ll a[maxn],b[maxn],c[maxn];
int tr[maxn];
void ntt(ll*f,bool type,int n){
	for(int i=0;i<n;i++)
		if(i<tr[i])
			swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		ll tG=qpow(type?G:invG,(P-1)/p);
		for(int k=0;k<n;k+=p){
			ll buf=1;
			for(int l=k;l<k+len;l++){
				ll temp=buf*f[l+len]%P;
				qmod(f[l+len]=f[l]-temp);
				qmod(f[l]=f[l]+temp-P);
				buf=buf*tG%P;
			}
		}
	}
}
void poly_mul(ll*f,ll*g,ll*h,int n,int m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	ntt(f,true,n),ntt(g,true,n);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i]%P;
	ntt(f,false,n);
	ll invn=qpow(n);
	for(int i=0;i<n;i++)h[i]=((f[i]*invn%P+P)%P);
}
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<=n+m;i++)write(c[i]),putchar(i!=n+m?' ':'\n');
	return 0;
}