记录编号	359205	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2014] 力	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.417 s
提交时间	2016-12-21 15:03:28	内存使用	91.84 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double db;
const int N=1e6+10;
const db pi=acos(-1.0);
db sqr(db x){return x*x;}
int n;
struct comp{
	db x,y;
	comp(db X=0,db Y=0){x=X;y=Y;}
	comp operator + (const comp a)const{return comp(x+a.x,y+a.y);}
	comp operator - (const comp a)const{return comp(x-a.x,y-a.y);}
	comp operator * (const comp a)const{return comp(x*a.x-y*a.y,x*a.y+y*a.x);}
	comp operator * (const db a)const{return comp(x*a,y*a);}
}w[N],a[N],b[N],temp[N];
void fft(int n,comp *a,int start,int step){
	if (n==1) return;
	int m=n>>1;
	fft(m,a,start,step<<1);
	fft(m,a,start+step,step<<1);
	for (int k=0;k<m;++k){
		int pos=2*k*step;
		temp[k]=a[start+pos]+w[k*step]*a[start+pos+step];
		temp[k+m]=a[start+pos]-w[k*step]*a[start+pos+step];
	}
	for (int i=0;i<n;++i)
		a[i*step+start]=temp[i];
}
int main()
{
	freopen("force.in","r",stdin);
	freopen("force.out","w",stdout);
	scanf("%d",&n);
	for (int i=0;i<n;++i) scanf("%Lf",&a[i].x);
	for (int i=1;i<=n;++i)
		b[n+i].x=1.0/sqr(i),b[n-i].x=-b[n+i].x;
	int size=1;
	while (size<4*n+2) size<<=1;
	w[0]=comp(1,0);
	w[1]=comp(cos(2*pi/size),sin(2*pi/size));
	for (int i=2;i<=size;++i) w[i]=w[i-1]*w[1];
	fft(size,a,0,1);fft(size,b,0,1);
	for (int i=0;i<size;++i) a[i]=a[i]*b[i];
	reverse(w,w+size+1);
	fft(size,a,0,1);
	for (int i=0;i<size;++i) a[i].x/=size;
	for (int i=n;i<n*2;i++) printf("%Lf\n",a[i].x);
	return 0;
}