我也不知道为什么大视野上没有题面描述,所以我就只能百度了。
首先这道题有个陷阱,题面给你的是Fj,但要求的是Ei,所以我们先把qi除掉,于是Ei就变成了sigma(j<i)(q[j]/(i-j)^2)-sigma(j>i)(q[j]/(i-j)^2)。
于是,我们令a[i]=q[i],b[i]=1/(i*i);
那么,E[i]=sigma(a[j]*b[i-j])-sigma(a[j]*b[j-i]);
神奇的发现,减号左右两边都是卷积的形式,FFT直接上就行了。
代码:
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; double pi=acos(-1); int n,m; struct cp{double x,y;}; double q[500010]; cp a[500010],b[500010],cur[500010],c[500010],d[500010],A[500010],B[500010]; cp operator *(cp x,cp y){return (cp){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};} cp operator +(cp x,cp y){return (cp){x.x+y.x,x.y+y.y};} cp operator -(cp x,cp y){return (cp){x.x-y.x,x.y-y.y};} void fft(cp *a,int n,int fl) { for (int i=n>>1,j=1;j<n;j++) { if (i<j) swap(a[i],a[j]); int k=n>>1; for (;k&i;i^=k,k>>=1);i^=k; } for (int m=2;m<=n;m<<=1) { cp w=(cp){cos(2*pi*fl/m),sin(2*pi*fl/m)}; cur[0]=(cp){1,0}; for (int i=1;i<=m;i++) cur[i]=cur[i-1]*w; for (int i=0;i<n;i+=m) for (int j=i;j<i+(m>>1);j++) { cp u=a[j],v=a[j+(m>>1)]*cur[j-i]; a[j]=u+v; a[j+(m>>1)]=u-v; } } } int main() { scanf("%d",&n); for (int i=0;i<n;i++) scanf("%lf",&q[i]); for (int i=0;i<n;i++) a[i].x=q[i]; for (int i=1;i<n;i++) b[i].x=(double)1/i/i; m=1;while (m<=n*2) m<<=1; fft(a,m,1);fft(b,m,1); for (int i=0;i<=m;i++) c[i]=a[i]*b[i]; fft(c,m,-1); for (int i=0;i<=m;i++) c[i].x=c[i].x/m; for (int i=0;i<n;i++) A[i].x=q[i]; for (int i=0;i<n-1;i++) B[i].x=(double)1/(n-1-i)/(n-1-i); fft(A,m,1);fft(B,m,1); for (int i=0;i<=m;i++) d[i]=A[i]*B[i]; fft(d,m,-1); for (int i=0;i<=m;i++) d[i].x=d[i].x/m; for (int i=0;i<n;i++) printf("%lf\n",c[i].x-d[n-1+i].x); }