【BZOJ】3527: [Zjoi2014]力

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3527

把${f_i}$消去之后换元就是卷积的形式，直接算就可以了。

---

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<complex>

 #include<cstring>

 using namespace std;

 #define maxn 1001000

 #define llg long long

 #define Pi acos(-1.0)

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 typedef complex<double> XU;

 struct FFT

 {

     llg rev[maxn],L,n;

     double c[maxn];

     void fft(XU *z,llg f)

     {

         for (llg i=;i<n;i++) if (i<rev[i]) swap(z[i],z[rev[i]]);

         for (llg i=;i<n;i*=)

         {

             XU wn(cos(Pi/i),sin(Pi/i));

             for (llg p=i*,j=;j<n;j+=p)

             {

                 XU w(,);

                 for (llg k=;k<i;k++,w*=wn)

                 {

                     XU x=z[j+k],y=z[j+k+i]*w;

                     z[j+k]=x+y,z[j+k+i]=x-y;

                 }

             }

         }

         if (f==-) reverse(z+,z+n);

     }

     XU a[maxn],b[maxn];

     void work()

     {

         llg m=(n-)*;

         for (n=;n<=m;n*=) L++;

         for (llg i=;i<n;i++) rev[i]=(rev[i/]/)|((i&)<<(L-));

         fft(a,),fft(b,);

         for (llg i=;i<n;i++) a[i]*=b[i];

         fft(a,-);

         for (llg i=;i<n;i++) c[i]=(a[i].real()/n);

     }

 }F1,F2;

 double x[maxn];

 int main()

 {

     yyj("li");

     llg N;

     cin>>N;

     F1.n=N;

     for (llg i=;i<N;i++) scanf("%lf",&x[i]),F1.a[i]=x[i];

     for (llg i=;i<=N-;i++) F1.b[i]=(double)-1.0/(double)(N--i)/(double)(N--i);

     for (llg i=N;i<=*N-;i++) F1.b[i]=(double)1.0/(double)(N--i)/(double)(N--i);

     F1.work();

     for (llg i=N-;i<*N-;i++) printf("%.9lf\n",F1.c[i]) ;

     return ;

 }