文件详细信息

下载本文件

本文件的大小为 1496 字节。

#include<cmath>
#include<cstdio>
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=0;
	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 int maxn=1<<20;
const double pi=acos(-1);
int n,m;
struct complex{
	double x,y;
	complex(double a=0,double b=0){x=a,y=b;}
}f[maxn<<1],g[maxn<<1],h[maxn<<1];
complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void fft(complex*f,int len,bool flag){
	if(len==1)return;
	complex*fl=f,*fr=fl+(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];
	fft(fl,len>>1,flag);
	fft(fr,len>>1,flag);
	complex tG(cos(2*pi/len),-sin(2*pi/len)),buf(1,0);
	if(!flag)tG.y*=-1;
	for(int k=0;k<len>>1;k++){
		h[k]=fl[k]+buf*fr[k];
		h[k+(len>>1)]=fl[k]-buf*fr[k];
		buf=buf*tG;
	}
	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); 
	fft(f,n,true),fft(g,n,true);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i];
	fft(f,n,false);
	for(int i=0;i<=m;i++)write(int(f[i].x/n+0.49)),putchar(i!=m?' ':'\n');
	return 0;
}