文件详细信息

下载本文件

本文件的大小为 1786 字节。

#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;
}
void write(int a){
	static int ch[20],cnt=0;
	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 dft(complex*f,int len){
	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];
	dft(fl,len>>1);
	dft(fr,len>>1);
	complex tG(cos(2*pi/len),sin(2*pi/len)),buf(1,0);
	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];
}
void idft(complex*f,int len){
	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];
	idft(fl,len>>1);
	idft(fr,len>>1);
	complex tG(cos(2*pi/len),-sin(2*pi/len)),buf(1,0);
	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); 
	dft(f,n),dft(g,n);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i];
	idft(f,n);
	for(int i=0;i<=m;i++)write(f[i].x/n+0.49),putchar(i!=m?' ':'\n');
	return 0;
}