1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
struct Complex{ double r,i; Complex(const double &_r=0,const double &_i=0):r(_r),i(_i){} Complex operator *(const Complex &v)const{ return Complex(r*v.r-i*v.i,r*v.i+i*v.r); } Complex operator +(const Complex &v)const{ return Complex(r+v.r,i+v.i); } Complex operator -(const Complex &v)const{ return Complex(r-v.r,i-v.i); } Complex operator /(const double &k)const{ return Complex(r/k,i/k); } Complex operator /(const Complex &v)const{ return Complex((i*v.i+r*v.r)/(v.r*v.r+v.i*v.i),(i*v.r-r*v.i)/(v.r*v.r+v.i*v.i)); } }; Complex omega(const double &k){return Complex(cos(k),sin(k));}
const int N=(2<<17)+10; const double PI=acos(-1.0);
int rev[N<<2];
void FFT(Complex *ary,int n,int typ){ for(int i=1;i<n;i++){ rev[i]=rev[i>>1]>>1|((i&1)*(n>>1)); if(rev[i]<i) swap(ary[rev[i]],ary[i]); } for(int i=1,ii=2;i<n;i<<=1,ii<<=1){ Complex wn=omega(PI/i*typ); for(int j=0;j<n;j+=ii){ Complex wi(1,0); for(int k=j;k<j+i;k++,wi=wi*wn){ Complex tmp=wi*ary[k+i]; ary[k+i]=ary[k]-tmp; ary[k]=ary[k]+tmp; } } } if(typ==-1) for(int i=0;i<n;i++) ary[i]=ary[i]/n; } void bluestein(Complex *ary,int n,int typ){ static Complex aryA[N<<2],aryB[N<<2]; memset(aryA,0,sizeof aryA); memset(aryB,0,sizeof aryB); for(int i=0;i<n;i++) aryA[i]=omega(-typ*PI*i*i/n)*ary[i]; for(int i=0;i<(n<<1);i++) aryB[i]=omega(typ*PI*(i-n)*(i-n)/n); int len=1; while(len<(n<<2)) len<<=1; FFT(aryA,len,1),FFT(aryB,len,1); for(int i=0;i<len;i++) aryA[i]=aryA[i]*aryB[i]; FFT(aryA,len,-1); for(int i=0;i<n;i++){ ary[i]=aryA[i+n]*omega(-typ*PI*i*i/n); if(typ==-1) ary[i]=ary[i]/n; } }
int n; Complex aryA[N],aryB[N];
int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf",&aryA[i].r); for(int i=0;i<n;i++) scanf("%lf",&aryB[i].r); bluestein(aryA,n,1),bluestein(aryB,n,1); for(int i=0;i<n;i++) aryA[i]=aryB[i]/aryA[i]; bluestein(aryA,n,-1); for(int i=0;i<n;i++) printf("%.4f\n",aryA[i].r); return 0; }
|