文件详细信息

下载本文件

本文件的大小为 1375 字节。

#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;
}
template<typename T>
void write(T a){
	static int ch[40],cnt;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
const ll P=998244353;
ll qmod(ll x){
    return x+((x>>63)&P);
}
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;
}
const int maxn=1<<20,maxm=1<<20;
const ll G=3,invG=qpow(G);
int n,m;
ll f[maxn<<1],g[maxn<<1],h[maxn<<1];
void ntt(ll*f,int len,bool type){
	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),ntt(fr,len>>1,type);
	ll tG=qpow(type?G:invG,(P-1)/len),buf=1;
	for(int k=0;k<len>>1;k++){
		h[k]=(fl[k]+buf*fr[k])%P;
		h[k+(len>>1)]=qmod(fl[k]-buf*fr[k]%P);
		buf=buf*tG%P;
	}
	for(int k=0;k<len;k++)f[k]=h[k];
}
int main(){
	n=read(),m=read();
	for(int i=0;i<=n;i++)f[i]=read();
	for(int i=0;i<=m;i++)g[i]=read();
	for(m+=n,n=1;n<=m;n<<=1);
	ntt(f,n,true),ntt(g,n,true);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i]%P;
	ntt(f,n,false);
	ll invn=qpow(n);
	for(int i=0;i<=m;i++)write(f[i]*invn%P),putchar(i!=m?' ':'\n');
	return 0;
}