好久没写过博客了。。

大力推式子就行了：

\(E_i=\sum_{j<i}\frac{q_j}{(i-j)^2}+\sum_{j>i}\frac{q_j}{(j-i)^2}\)

那么要转化成卷积的形式对吧，设\(f(i)=q_i,g(i)=\frac{1}{i^2}\)

\(E_i=\sum_{j<i}f(j)g(i-j)+\sum_{j>i}f(j)g(j-i)\)

直接NTT就行了。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

typedef std::complex<double> cp;

const double pi=acos(-1);

double q[100010];

int rev[1<<19];

cp A[1<<19],B[1<<19],omg[1<<19],inv[1<<19];

double ans[100010];

il vd fft(cp*A,int n,cp*omg){

    for(int i=0;i<n;++i)if(rev[i]>i)std::swap(A[i],A[rev[i]]);

    for(int o=1;o<n;o<<=1)

        for(cp*p=A;p!=A+n;p+=o<<1)

            for(int i=0;i<o;++i){

                cp t=omg[n/(o<<1)*i]*p[i+o];

                p[i+o]=p[i]-t,p[i]+=t;

            }

}

int main(){

    int n=gi();

    for(int i=1;i<=n;++i)scanf("%lf",&q[i]);

    int N=1,lg=0;while(N<(n+2)*2)N<<=1,++lg;

    for(int i=0;i<N;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);

    for(int i=0;i<N;++i)omg[i]=cp(cos(2*pi*i/N),sin(2*pi*i/N)),inv[i]=conj(omg[i]);

    for(int i=1;i<=n;++i)A[i]=1.0/i/i;

    for(int i=1;i<=n;++i)B[i]=q[i];

    fft(A,N,omg),fft(B,N,omg);

    for(int i=0;i<N;++i)A[i]*=B[i];

    fft(A,N,inv);

    for(int i=0;i<N;++i)A[i]/=N;

    for(int i=1;i<=n;++i)ans[i]=A[i].real();

    memset(A,0,sizeof A);memset(B,0,sizeof B);

    std::reverse(q+1,q+n+1);

    for(int i=1;i<=n;++i)A[i]=1.0/i/i;

    for(int i=1;i<=n;++i)B[i]=q[i];

    fft(A,N,omg),fft(B,N,omg);

    for(int i=0;i<N;++i)A[i]*=B[i];

    fft(A,N,inv);

    for(int i=0;i<N;++i)A[i]/=N;

    for(int i=1;i<=n;++i)ans[n-i+1]-=A[i].real();

    for(int i=1;i<=n;++i)printf("%.3lf\n",ans[i]);

    return 0;

}