题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3527
首先卷积的形式是$h(i)=\sum_{i=0}^jf(i)g(i-j)$，如果我们可以把式子整理成这个样子再套上FFT就成功了。
$$E_i=\sum_{j<i}\frac{q_j}{(j-i)^2}-\sum_{j>i}\frac{q_j}{(i-j)^2}$$
$$E_i=\sum_{j=0}^{i-1}\frac{q_j}{(j-i)^2}^2-\sum_{j=0}^{n-i-1}\frac{q_{n-j}}{(n-i-j)^2}$$
令$f(i)=q_i$，$g(i)=\frac{1}{i^2}$，$t(i)=q_{n-i}$，则有
$$E_i=\sum_{j=0}^{i-1}f(i)g(i-j)-\sum_{j=0}^{n-i-1}t(j)g(n-i-j)$$
因为$j$无法取到$i$或者$n-i$，所以令$g(0)=0$来消除最后一项的影响。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double pi=acos(-1.0);
struct complex{
double r,i;
complex (double _r=,double _i=){
r=_r,i=_i;
}
complex operator + (const complex &_){
return complex(r+_.r,i+_.i);
}
complex operator - (const complex &_){
return complex(r-_.r,i-_.i);
}
complex operator * (const complex &_){
return complex(r*_.r-i*_.i,r*_.i+_.r*i);
}
};
void reverse(complex y[],int len){
for(int i=,j=len>>,k;i+<len;i++){
if(i<j) swap(y[i],y[j]);
k=len>>;
while(j>=k){
j-=k;
k>>=;
}
if(j<k) j+=k;
}
}
void FFT(complex y[],int len,int on){
reverse(y,len);
for(int h=;h<=len;h<<=){
complex wn(cos(-on**pi/h),sin(-on**pi/h));
for(int j=;j<len;j+=h){
complex w(,);
for(int k=j;k<j+(h>>);k++){
complex u=y[k],t=w*y[k+(h>>)];
y[k]=u+t;
y[k+(h>>)]=u-t;
w=w*wn;
}
}
}
if(on==-) for(int i=;i<len;i++) y[i].r/=len;
}
double q[],ans[];
complex a[],b[],c[];
int main(){
int n,len=;
scanf("%d",&n);
while(len<n) len<<=;len<<=;
for(int i=;i<n;i++) scanf("%lf",&q[i]);
for(int i=;i<n;i++) a[i]=complex(q[i],);
for(int i=;i<n;i++) b[i]=complex(1.0/i/i,);
for(int i=n;i<len;i++) a[i]=b[i]=complex();
b[]=complex();
FFT(a,len,);
FFT(b,len,);
for(int i=;i<len;i++) c[i]=a[i]*b[i];
FFT(c,len,-);
for(int i=;i<n;i++) ans[i]=c[i].r;
for(int i=;i<n;i++) a[i]=complex(q[n-i-],);
for(int i=;i<n;i++) b[i]=complex(1.0/i/i,);
for(int i=n;i<len;i++) a[i]=b[i]=complex();
b[]=complex();
FFT(a,len,);
FFT(b,len,);
for(int i=;i<len;i++) c[i]=a[i]*b[i];
FFT(c,len,-);
for(int i=;i<n;i++) ans[i]-=c[n-i-].r;
for(int i=;i<n;i++) printf("%.3lf\n",ans[i]);
return ;
}