记录编号	271191	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2014] 力	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	3.147 s
提交时间	2016-06-15 18:44:18	内存使用	45.60 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=600010;
const long double PI=acos(-1.0);
struct complex{
	long double r,i;
	complex(long double r_=0.0,long double i_=0.0){
		r=r_;i=i_;
	}
	complex operator+(complex a){
		return complex(r+a.r,i+a.i);
	}
	complex operator-(complex a){
		return complex(r-a.r,i-a.i);
	}
	complex operator*(complex a){
		return complex(r*a.r-i*a.i,i*a.r+r*a.i);
	}
}A[maxn],B[maxn],C[maxn];
 
void Rader(complex *a,int len){
	for(int i=1,j=len>>1;i<len-1;i++){
		if(i<j)swap(a[i],a[j]);
		int k=len>>1;
		while(j>=k){
			j-=k;
			k>>=1;
		}
		j+=k;
	}
}
 
void FFT(complex *a,int len,int on){
	Rader(a,len);
	for(int h=2;h<=len;h<<=1){
		complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
		for(int j=0;j<len;j+=h){
			complex w(1,0);
			for(int k=j;k<j+(h>>1);k++){
				complex x=a[k];
				complex y=a[k+(h>>1)]*w;
				a[k]=x+y;
				a[k+(h>>1)]=x-y;
				w=w*wn;
			}
		}
	}
	if(on==-1)
		for(int i=0;i<len;i++)
			a[i].r/=len;		
}
 
double f[maxn],E[maxn];
int main(){
#ifndef ONLINE_JUDGE
	freopen("force.in","r",stdin);
	freopen("force.out","w",stdout);
#endif	
	int n,len=1;
	scanf("%d",&n);
	while(len<=n*2)len<<=1;
	for(int i=1;i<=n;i++)
		scanf("%lf",&f[i]);
	
	for(int i=1;i<=n;i++){
		A[i-1].r=f[i];
		B[n-i].r=f[i];
		C[i].r=1.0/(1ll*i*i);
	}
	FFT(A,len,1);FFT(B,len,1);FFT(C,len,1);
	for(int i=0;i<len;i++)
		A[i]=A[i]*C[i],B[i]=B[i]*C[i];
	FFT(A,len,-1);FFT(B,len,-1);
	for(int i=0;i<n;i++){
		E[i]=A[i].r-B[n-i-1].r;
		printf("%.3f\n",E[i]);
	}	
	return 0;
}