文件详细信息

下载本文件

本文件的大小为 1487 字节。

#include<cmath>
#include<cstdio>
template<typename T>
inline void swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
typedef long long ll;
typedef double real;
struct Complex{
	real x,y;
	Complex(const real _x=0,const real _y=0){
		x=_x,y=_y;
	}
};
Complex operator+(const Complex a,const Complex b){
	return Complex{a.x+b.x,a.y+b.y};
}
Complex operator-(const Complex a,const Complex b){
	return Complex{a.x-b.x,a.y-b.y};
}
Complex operator*(const Complex a,const Complex b){
	return Complex{a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
const int maxn=1<<17;
const real pi=acos(-1);
int n,m,_n,tr[maxn<<1];
Complex a[maxn<<1],b[maxn<<1],c[maxn<<1];
void fft(Complex*f,int mode){
	for(int i=0;i<n;i++)
		if(i<tr[i])
			swap(f[tr[i]],f[i]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		Complex tG(cos(2*pi/p),sin(2*pi/p)*mode);
		for(int k=0;k<n;k+=p){
			Complex buf(1,0);
			for(int l=k;l<k+len;l++){
				Complex tmp=buf*f[l+len];
				f[l+len]=f[l]-tmp;
				f[l]=f[l]+tmp;
				buf=buf*tG;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	_n=n;
	for(int i=0;i<n;i++)scanf("%lf",&a[i].x);
	for(int i=0;i<n;i++)b[i].x=c[n-i-1].x=1.0/(ll(i+1)*(i+1));
	for(m=n*2,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)+(i&1?n>>1:0);
	fft(a,1),fft(b,1),fft(c,1);
	for(int i=0;i<n;i++)b[i]=b[i]*a[i];
	for(int i=0;i<n;i++)c[i]=c[i]*a[i];
	fft(b,-1),fft(c,-1);
	for(int i=0;i<n;i++)b[i].x/=n;
	for(int i=0;i<n;i++)c[i].x/=n;
	for(int j=1;j<=_n;j++)printf("%.3lf\n",(j>=2?b[j-2].x:0)-c[_n+j-1].x);
	return 0;
}