#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e5+5;
const double PI=acos(-1.0);
struct Complex{
double real,imag;
Complex(double a=0,double b=0):real(a),imag(b){}
Complex(const Complex &a):real(a.real),imag(a.imag){}
Complex conj()const{return Complex(real,-imag);}
Complex &operator=(const Complex &a){real=a.real,imag=a.imag;return *this;}
Complex &operator+=(const Complex &a){real+=a.real,imag+=a.imag;return *this;}
Complex &operator-=(const Complex &a){real-=a.real,imag-=a.imag;return *this;}
Complex &operator*=(const Complex &a){
double tmp1=real*a.real-imag*a.imag,tmp2=real*a.imag+imag*a.real;
real=tmp1,imag=tmp2;return *this;
}
Complex &operator/=(const Complex &a){
double tmp1=(real*a.real+imag*a.imag)/(a.real*a.real+a.imag*a.imag),
tmp2=(imag*a.real-real*a.imag)/(a.real*a.real+a.imag*a.imag);
real=tmp1,imag=tmp2;return *this;
}
friend Complex operator+(const Complex &a,const Complex &b){Complex c(a);return c+=b;}
friend Complex operator-(const Complex &a,const Complex &b){Complex c(a);return c-=b;}
friend Complex operator*(const Complex &a,const Complex &b){Complex c(a);return c*=b;}
friend Complex operator/(const Complex &a,const Complex &b){Complex c(a);return c/=b;}
}eps[N],a[N],b[N];
void init(int n){
int l=n>>1;
for(int i=0;i<l;++i){
eps[l+i].real=cos(i*PI/l);
eps[l+i].imag=sin(i*PI/l);
}
while(l>>=1){
for(int i=0;i<l;++i){
eps[l+i]=eps[l+i<<1];
}
}
}
void dft(int n,Complex x[]){
for(int i=0,j=0;i<n;++i){
if(i<j)swap(x[i],x[j]);
for(int k=n>>1;(j^=k)<k;k>>=1){}
}
for(int i=2;i<=n;i<<=1){
int l=i>>1;
for(int j=0;j<n;j+=i){
for(int k=0;k<l;++k){
Complex u=x[k+j],v=eps[l+k]*x[k+j+l];
x[k+j]=u+v;
x[k+j+l]=u-v;
}
}
}
}
void idft(int n,Complex x[]){
reverse(x+1,x+n);
dft(n,x);
for(int i=0;i<n;++i)x[i]/=n;
}
int main(){
#ifdef LOCAL
freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
int t;
for(int i=0;i<=n;++i){
cin>>t;
a[i].real=t;
}
for(int i=0;i<=m;++i){
cin>>t;
a[i].imag=t;
}
int len=1;
while(len<n+m+2)len<<=1;
init(len);
dft(len,a);
for(int i=0;i<len;++i){
a[i]*=a[i];
}
idft(len,a);
for(int i=0;i<=n+m;++i){
cout<<static_cast<int>(a[i].imag/2.0+0.5)<<' ';
}
return 0;
}
Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |