文件详细信息

下载本文件

本文件的大小为 1580 字节。

#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]);
}
typedef double real;
struct Complex{
	real x,y;
	Complex(const real a=0,const real b=0){
		x=a,y=b;
	}
};
Complex operator+(const Complex a,const Complex b){
	return Complex{a.x+b.x,a.y+b.y};
}
Complex operator-(const Complex a,const Complex b){
	return Complex{a.x-b.x,a.y-b.y};
}
Complex operator*(const Complex a,const Complex b){
	return Complex{a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
template<typename T>
inline void swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
const int maxn=1<<20|5;
const real pi=acos(-1);
int n,m,tr[maxn<<1];
Complex f[maxn<<1],g[maxn<<1];
void fft(Complex*f,int type){
	for(int i=0;i<n;i++)
		if(i<tr[i])
			swap(f[tr[i]],f[i]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		Complex tG(cos(2*pi/p),sin(2*pi/p)*type);
		for(int k=0;k<n;k+=p){
			Complex buf(1,0);
			for(int l=k;l<k+len;l++){
				Complex temp=buf*f[l+len];
				f[l+len]=f[l]-temp;
				f[l]=f[l]+temp;
				buf=buf*tG;
			}
		}
	}
}
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);
	fft(f,1);
	fft(g,1);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i];
	fft(f,-1);
	for(int i=0;i<=m;i++)write(f[i].x/n+0.49),putchar(i!=m?' ':'\n');
	return 0;
}