题目链接：力
听说这道题是\(FFT\)板子题，于是我就来写了……
首先可以发现这个式子：\[E_i=\sum_{j<i}\frac{q_j}{(i-j)^2}-\sum_{j>i}\frac{q_j}{(i-j)^2} \]
然后可以对两半分别考虑一下。发现下标刚好是\(j+(i-j)=i\)，于是我们就可以开始构(gao)造(shi)了，弄俩多项式出来：
\[A_1(x)=0x^0+q_1x^1+q_2x^2+……+q_nx^n\]
\[A_2(x)=\frac{-1}{n^2}x^0+\frac{-1}{(n-1)^2}x^1+……+0x^n+……+\frac{1}{(n-1)^2}x^{2n-1}+\frac{1}{n^2}x^{2n}\]
把这两个多项式乘起来，取下标为\((n,2n]\)的系数即为答案。
实际上，把多函数\(A_1(x)\)的系数全部左移一位也是可以的，只不过答案的区间要变一下。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<complex>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define C complex<double>
#define maxn 300010
#define pi (acos(-1))
using namespace std;
typedef double llg;
int n,m,L,R[maxn];
C a[maxn],b[maxn];
llg gi(int x){return 1.0*x*x;}
void fft(C *a){
for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1){
C wn(cos(pi/i),sin(pi/i)),x,y;
for(int j=0;j<n;j+=(i<<1)){
C w(1,0);
for(int k=0;k<i;k++,w*=wn){
x=a[j+k]; y=w*a[j+i+k];
a[j+k]=x+y; a[j+i+k]=x-y;
}
}
}
}
int main(){
File("a");
scanf("%d",&n); m=n;
for(int i=0;i<n;i++) scanf("%lf",&a[i].real());
for(int i=0;i<n;i++) b[i].real()=-1.0/gi(n-i),b[2*n-i]=-b[i];
for(n=1;n<=(m<<1);n<<=1) L++;
for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
fft(a); fft(b);
for(int i=0;i<n;i++) a[i]*=b[i];
fft(a); reverse(a+1,a+n);
for(int i=m+1;i<=(m<<1);i++) printf("%.6lf\n",a[i].real()/n);
return 0;
}
原文：http://www.cnblogs.com/lcf-2000/p/6371720.html