[ZJOI2014]力

链接：https://www.luogu.com.cn/problem/P3338

题目描述：题目已经说的很清楚了吧。

题解：我们可以知道\(E_{j}=\sum_{i=1}^{j-1}\frac{q_{i}}{(j-i)^2}-\sum_{i=j+1}^{n}\frac{q_{i}}{(j-i)^2}\)

容易发现前面是一个卷积的形式，关键看后面：

令\(t_{j}=\sum_{i=j+1}^{n}\frac{q_{i}}{(j-i)^2}\)

令\(h_{i}=q_{n-i},k_{i}=t_{n-i+1}\)

则\(t_{j}=\sum_{i=j+1}^{n}\frac{q_{n-i+1}}{(j-i)^2}\)

\(t_{j}=\sum_{i=1}^{n-j}\frac{q_{n-i+1}}{(n-j-i+1)^2}\)

则有\(k_{j}=t_{n-j}=\sum_{i=1}^{j}\frac{q_{n-i+1}}{(j-i)^2}\)

则\(k_{j}=\sum_{i=1}^{j}\frac{k_{i}}{(j-i)^2}\)

容易发现这也是一个卷积的形式，跑\(FFT\)就行了。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct complex
{
	double x,y;
};
const double Pi=asin(1)*2;
complex a[2000001],b[2000001],c[2000001],d[2000001],w,wn;
double q[2000001],ans[2000001]; 
complex make_complex(double a,double b)
{
	complex temp;
	temp.x=a;
	temp.y=b;
	return temp;
}
complex add(complex a,complex b)
{
	return make_complex(a.x+b.x,a.y+b.y);
}
complex myminus(complex a,complex b)
{
	return make_complex(a.x-b.x,a.y-b.y);
} 
complex mul(complex a,complex b)
{
	return make_complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y);
}
void FFT(int limit,complex *s,int type)
{
	if (limit==1)
		return;
	complex a2[limit/2+1],b2[limit/2+1];
	for (int i=0;i<limit;i+=2)
	{
		a2[i/2]=s[i];
		b2[i/2]=s[i+1];
	}
	FFT(limit/2,a2,type);
	FFT(limit/2,b2,type);
	w=make_complex(cos(2*Pi/limit),type*sin(2*Pi/limit));
	wn=make_complex(1,0);
	for (int i=0;i<limit/2;++i,wn=mul(w,wn))
	{
		s[i]=add(a2[i],mul(wn,b2[i]));
		s[i+limit/2]=myminus(a2[i],mul(wn,b2[i]));
	}
	return;
}
int main()
{
	int n,limit=1;
	cin>>n;
	for (int i=1;i<=n;++i)
		cin>>q[i];
	for (int i=1;i<=n;++i)
		a[i].x=1.0/i/i;
	for (int i=1;i<=n;++i)
		b[i].x=q[i];
	while (limit<=2*n)
		limit*=2;
	FFT(limit,a,1);
	FFT(limit,b,1);
	for (int i=0;i<=limit;++i)
		c[i]=mul(a[i],b[i]);
	FFT(limit,c,-1);
	for (int i=1;i<=n;++i)
		ans[i]=c[i].x/limit;
	for (int i=1;i<=n;++i)
		d[i].x=q[n-i+1];
	FFT(limit,d,1);
	for (int i=0;i<=limit;++i)
		c[i]=mul(a[i],d[i]);
	FFT(limit,c,-1);
	for (int i=1;i<=n;++i)
		ans[i]-=c[n-i+1].x/limit;
	for (int i=1;i<=n;++i)
		printf("%0.3lf\n",ans[i]);
	return 0;
}