https://www.luogu.com.cn/problem/P3338

#include<bits/stdc++.h>
// #define int long long
#define double long double
using namespace std;
const int N=1e6+10;
const int C=32768;
int p,x;
const double PI = acos(-1);
struct Complex{
    double x,y;
    Complex operator+(const Complex &t){return {x+t.x,y+t.y};}
    Complex operator-(const Complex &t){return {x-t.x,y-t.y};}
    Complex operator*(const Complex &t){return {x*t.x-y*t.y,x*t.y+y*t.x};}
}a[N],b[N],a2[N],c[N];
int n,m,tot=1,bit,r[N];
void fft(Complex a[],int inv){
    for(int i=0;i<tot;i++){
        if(i<r[i])swap(a[i],a[r[i]]);
    }
    for(int mid=1;mid<tot;mid*=2){
        auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
        for(int i=0;i<tot;i+=mid*2){
            auto wk=Complex({1,0});
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y;
                a[i+j+mid]=x-y;
            }
        }
    }
    if(inv==1)return;
    for(int i=0;i<tot;i++)a[i].x/=tot,a[i].y/=tot;
}
signed main(){
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++){
        //scanf("%lf",&a[i].x);
        cin>>a[i].x;
        a2[n-i].x=a[i].x;
        // c[n-i].x=a[i].x;
        b[i].x=(double)(1.0 / i / i);
    }
    while(tot<=n*2)tot*=2,bit++;
    //cout<<"tot="<<tot<<endl;
    for(int i=0;i<tot;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),fft(b,1),fft(a2,1);
    for(int i=0;i<tot;i++){
        a[i]=a[i]*b[i];
        a2[i]=a2[i]*b[i];
        c[i]=c[i]*b[i];
    }
    fft(a,-1),fft(a2,-1);

    for(int i=1;i<=n;i++){
        double ans=a[i].x-a2[n-i].x;
        cout<<fixed<<ans<<'\n';
    }
}