BZOJ3527: [Zjoi2014]力

#include<bits/stdc++.h>
#define RG register
#define il inline
#define db double
#define LL long long
#define N 1000000
using namespace std;
typedef complex<db>W;
const db pi=acos(-1);
W f[N],F[N],G[N];
int rev[N],n,L;
void FFT(W * A,int f){
  for(int i=0;i<n;++i)if(i>rev[i])swap(A[i],A[rev[i]]);
  for(int i=1;i<n;i<<=1){
    W wn(cos(pi/i),sin(f*pi/i)),x,y;
    for(int j=0;j<n;j+=(i<<1)){
      W w(1,0);
      for(int k=0;k<i;k++,w*=wn){
    x=A[j+k],y=w*A[j+k+i];
    A[j+k]=x+y;
    A[j+k+i]=x-y;
      }
    }
  }
  if(f==-1)for(int i=0;i<n;++i)A[i].real()/=n;
}
int main(){
  scanf("%d",&n);n--;
  for(int i=0;i<=n;++i){
    db x;
    scanf("%lf",&x);
    f[i]=F[n-i]=x;
  }
  int m=2*n;
  for(LL i=1;i<=n;++i)G[i]=(1.0/(i*i));
  for(n=1;n<=m;n<<=1)L++;
  for(int i=0;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
  FFT(f,1),FFT(G,1);FFT(F,1);
  for(int i=0;i<n;++i)f[i]*=G[i];
  for(int i=0;i<n;++i)F[i]*=G[i];
  FFT(f,-1);FFT(F,-1);
  for(int i=0;i<=m/2;++i)printf("%.3lf\n",(f[i].real()-F[(m/2)-i].real()));
  return 0;
}