注释版

#include<bits/stdc++.h>
using namespace std;
constexpr int M=4e5+10; 
const double pi=acos(-1.0);
complex<double> A[M],B[M],C[M];
void FFT(complex<double> a[],int n,int x){
    if(n==1) return;
    complex<double> A1[n/2],A2[n/2];
    for(int i=0;i<n/2;i++){
        A1[i]=a[i*2];
        A2[i]=a[i*2+1];
    }
    FFT(A1,n/2,x);FFT(A2,n/2,x);
    complex<double> w0(1,0),wn(cos(2*pi/n),x*sin(2*pi/n));
    for(int i=0;i<n/2;++i,w0*=wn){
        a[i]=A1[i]+w0*A2[i];
        a[i+n/2]=A1[i]-w0*A2[i];
    }
}
int main(){
	int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        double x; scanf("%lf",&x);
        A[i]={x,0};
        B[n+1-i]={x,0};
    }
    // 构造C数组，C[i] = 1/i^2  (i从1到n） 
    for(int i=1;i<=n;i++) C[i]={1.0/i/i,0};
    // 计算合适的FFT长度N
	int N=1<<(int)log2(2*n)+1;
    // 对A、B、C分别做FFT正变换
    FFT(A,N,1);FFT(B,N,1);FFT(C,N,1);
    // 频域相乘：A = A*C，B = B*C
    for(int i=0;i<N;i++) A[i]*=C[i], B[i]*=C[i];
    // 逆变换回时域
    FFT(A,N,-1);FFT(B,N,-1);
    // 逆变换后需要除以长度N
    for(int i=0;i<N;i++) A[i]/=N, B[i]/=N;
    // 输出结果：Ei = A[i] - B[n+1-i] (因为B翻转后对应后半部分卷积)
    for(int i=1;i<=n;i++)
        printf("%.4lf\n",-B[n+1-i].real()+A[i].real());
    return 0;
}

无注释版

#include<bits/stdc++.h>
using namespace std;
constexpr int M=4e5+10; 
const double pi=acos(-1.0);
complex<double> A[M],B[M],C[M];
void FFT(complex<double> a[],int n,int x){
    if(n==1) return;
    complex<double> A1[n/2],A2[n/2];
    for(int i=0;i<n/2;i++){
        A1[i]=a[i*2];
        A2[i]=a[i*2+1];
    }
    FFT(A1,n/2,x);FFT(A2,n/2,x);
    complex<double> w0(1,0),wn(cos(2*pi/n),x*sin(2*pi/n));
    for(int i=0;i<n/2;++i,w0*=wn){
        a[i]=A1[i]+w0*A2[i];
        a[i+n/2]=A1[i]-w0*A2[i];
    }
}
int main(){
	int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        double x; scanf("%lf",&x);
        A[i]={x,0};
        B[n+1-i]={x,0};
    }
    for(int i=1;i<=n;i++) C[i]={1.0/i/i,0};
	int N=1<<(int)log2(2*n)+1;
    FFT(A,N,1);FFT(B,N,1);FFT(C,N,1);
    for(int i=0;i<N;i++) A[i]*=C[i], B[i]*=C[i];
    FFT(A,N,-1);FFT(B,N,-1);
    for(int i=0;i<N;i++) A[i]/=N, B[i]/=N;
    for(int i=1;i<=n;i++)
        printf("%.4lf\n",-B[n+1-i].real()+A[i].real());
    return 0;
}

版权为zzy（修改了下码风。。。） 底层逻辑还是NTT

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
const int N=4e5+10;
complex<double>a[N],b[N],c[N];
int n,x;
void NTT(complex<double> a[],int n,int x)
{
    if(n==1)return;
    complex<double>a1[n/2],a2[n/2];
    for(int i=0;i<n/2;i++)a1[i]=a[i*2],a2[i]=a[i*2+1];
    NTT(a1,n/2,x);NTT(a2,n/2,x);
    complex<double>w0(1,0),wn(cos(2*pi/n),x*sin(2*pi/n));
    for(int i=0;i<n/2;i++,w0*=wn)
	{
        a[i]=a1[i]+w0*a2[i];
        a[i+n/2]=a1[i]-w0*a2[i];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
	{
        double x;scanf("%lf",&x);
        a[i]={x,0};
        b[n+1-i]={x,0};
    }
    for(int i=1;i<=n;i++)c[i]={1.0/i/i,0};
	x=1<<(int)log2(2*n)+1;
    NTT(a,x,1);NTT(b,x,1);NTT(c,x,1);
    for(int i=0;i<x;i++)a[i]*=c[i],b[i]*=c[i];
    NTT(a,x,-1);NTT(b,x,-1);
    for(int i=0;i<x;i++)a[i]/=x,b[i]/=x;
    for(int i=1;i<=n;i++)printf("%.4lf\n",-b[n+1-i].real()+a[i].real());
    return 0;
}