文件详细信息

下载本文件

本文件的大小为 1424 字节。

#include<cstdio>
typedef long long ll;
const ll P=998244353;
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]);
}
inline void qmod(ll&x){
	x=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|10;
const ll G=3,invG=qpow(G);
int n,m;
ll f[maxn<<1],g[maxn<<1];
void swap(ll&a,ll&b){
	ll temp=a;
	a=b;
	b=temp;
}
int tr[maxn<<1];
void ntt(ll*f,bool type){
	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;
			}
		}
	}
}
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);
	for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	ntt(f,true),ntt(g,true);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i]%P;
	ntt(f,false);
	ll invn=qpow(n);
	for(int i=0;i<=m;i++)write(int(f[i]*invn%P)),putchar(i!=m?' ':'\n');
	return 0;
}