n行,第i行输出Ei。与标准答案误差不超过1e-2即可。
Sample Input5 4006373.885184 15375036.435759 1717456.469144 8514941.004912 1410681.345880Sample Output-16838672.693 3439.793 7509018.566 4595686.886 10903040.872
先除掉qj
前后两部分分开算,
前面一部分就是一个普通的卷积、
后边一部分要搞一下,如果前一部分是i+j是一个定值的话,那后面的一部分就是i-j是一个定值
对于这种情况就需要将一个数组翻转一下,
求出来的最后的结果也是翻转的。
需要在翻过来
1 #include"bits/stdc++.h" 2 #define sd(x) scanf("%d",&(x)); 3 #define sf(x) scanf("%lf",&(x)); 4 #define sld(x) scanf("%lld",&(x)); 5 using namespace std; 6 7 const int maxn = 2e6+10; 8 const double Pi = acos(-1.0); 9 struct cp 10 { 11 double x,y; 12 cp (double xx=0,double yy=0) 13 {x=xx,y=yy;} 14 }a[maxn],g[maxn],b[maxn]; 15 16 cp operator + (cp a,cp b){ return cp(a.x+b.x , a.y+b.y);} 17 cp operator - (cp a,cp b){ return cp(a.x-b.x , a.y-b.y);} 18 cp operator * (cp a,cp b){ return cp(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}//不懂的看复数的运算那部分 19 20 int n,m; 21 int l,r[maxn]; 22 int limit = 1; 23 24 25 inline void fft(cp *a,int ff) 26 { 27 for(int i=0;i<limit;i++) 28 if(i<r[i])swap(a[i],a[r[i]]); 29 for(int mid=1;mid<limit;mid<<=1) 30 { 31 cp wn(cos(Pi/mid) , ff*sin(Pi/mid)); 32 for(int R=mid<<1,j=0;j<limit;j+=R) 33 { 34 cp w(1,0); 35 for(int k=0;k<mid;k++,w=w*wn) 36 { 37 cp x=a[j+k],y=w*a[j+mid+k]; 38 a[j+k]=x+y; 39 a[j+mid+k]=x-y; 40 } 41 } 42 43 } 44 45 } 46 47 int main() 48 { 49 50 sd(n); 51 for(int i=1;i<=n;i++)sf(a[i].x); 52 for(int i=1;i<=n;i++)b[i]=a[n-i+1]; 53 54 55 while(limit<=2*n) limit<<=1,l++; 56 // cout<<"LIMIT: "<<limit<<endl; 57 for(int i=0;i<limit;i++) 58 r[i]=(r[i>>1]>>1)|( (i&1)<<(l-1)); 59 60 for(int i=1;i<=n;i++) 61 g[i].x=1.0/(1.0*i*i); 62 //for(int i=1;i<=10;i++)cout<<g[i].x<<" ";cout<<endl; 63 64 65 fft(a,1); fft(b,1); fft(g,1); 66 67 for(int i=0;i<=limit;i++)a[i]=a[i]*g[i],b[i]=b[i]*g[i]; 68 fft(a,-1); fft(b,-1); 69 /* for(int i=1;i<=n;i++) 70 printf("%.3f ",b[i].x ); cout<<endl; 71 */ 72 for(int i=1;i<=n;i++) 73 printf("%.3f\n",a[i].x/limit - b[n-i+1].x/limit ); 74 return 0; 75 76 77 78 79 }