力 HYSBZ

给出n个数qi，给出Fj的定义如下：

令Ei=Fi/qi，求Ei.

 

Input

第一行一个整数n。

接下来n行每行输入一个数，第i行表示qi。

n≤100000，0<qi<1000000000

 

 

Output

 n行，第i行输出Ei。与标准答案误差不超过1e-2即可。

Sample Input5 4006373.885184 15375036.435759 1717456.469144 8514941.004912 1410681.345880

Sample Output-16838672.693 3439.793 7509018.566 4595686.886 10903040.872

---

---

---

---

先除掉qj

前后两部分分开算，

前面一部分就是一个普通的卷积、

后边一部分要搞一下，如果前一部分是i+j是一个定值的话，那后面的一部分就是i-j是一个定值

对于这种情况就需要将一个数组翻转一下， 

求出来的最后的结果也是翻转的。

需要在翻过来

---

---

---

#include"bits/stdc++.h"
#define sd(x) scanf("%d",&(x));
#define sf(x) scanf("%lf",&(x));
#define sld(x) scanf("%lld",&(x));
using namespace std;

const int maxn = 2e6+10;
const double Pi = acos(-1.0);
struct cp
{
    double x,y;
    cp (double xx=0,double yy=0)
    {x=xx,y=yy;}
}a[maxn],g[maxn],b[maxn];

cp operator + (cp a,cp b){ return cp(a.x+b.x , a.y+b.y);}
cp operator - (cp a,cp b){ return cp(a.x-b.x , a.y-b.y);}
cp operator * (cp a,cp b){ return cp(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}//不懂的看复数的运算那部分

int n,m;
int l,r[maxn];
int limit = 1;


inline void fft(cp *a,int ff)
{
    for(int i=0;i<limit;i++)
    if(i<r[i])swap(a[i],a[r[i]]);
    for(int mid=1;mid<limit;mid<<=1)
        {
        cp wn(cos(Pi/mid) , ff*sin(Pi/mid));
        for(int R=mid<<1,j=0;j<limit;j+=R)
        {
            cp w(1,0);
            for(int k=0;k<mid;k++,w=w*wn)
            {
                cp x=a[j+k],y=w*a[j+mid+k];
                a[j+k]=x+y;
                a[j+mid+k]=x-y;
            }
        }

    }

}

int main()
{

   sd(n);
   for(int i=1;i<=n;i++)sf(a[i].x);
   for(int i=1;i<=n;i++)b[i]=a[n-i+1];


   while(limit<=2*n) limit<<=1,l++;
  // cout<<"LIMIT: "<<limit<<endl;
   for(int i=0;i<limit;i++)
   r[i]=(r[i>>1]>>1)|( (i&1)<<(l-1));

   for(int i=1;i<=n;i++)
    g[i].x=1.0/(1.0*i*i);
  //for(int i=1;i<=10;i++)cout<<g[i].x<<" ";cout<<endl;


   fft(a,1); fft(b,1); fft(g,1);

   for(int i=0;i<=limit;i++)a[i]=a[i]*g[i],b[i]=b[i]*g[i];
   fft(a,-1);  fft(b,-1);
 /*  for(int i=1;i<=n;i++)
   printf("%.3f ",b[i].x ); cout<<endl;
*/
   for(int i=1;i<=n;i++)
   printf("%.3f
",a[i].x/limit - b[n-i+1].x/limit );
   return 0;




}