求助一道大水题,悬两关
查看原帖
求助一道大水题,悬两关
690355
xyzqwq楼主2023/11/14 17:38
#include<bits/stdc++.h>
using namespace std;
typedef complex<double>cp;
const double pi=acos(-1);
const int N=4e5+10;
int n,m;
cp f[N],g[N],g2[N];
void FFT(cp* a,int n,int type){
        if(!n) return;
        cp a0[n+10],a1[n+10];
        for(int i=0;i<n;i++) a0[i]=a[i*2],a1[i]=a[i*2+1];
        FFT(a0,n/2,type),FFT(a1,n/2,type);
        cp W(cos(pi/n),type*sin(pi/n)),w(1,0);
        for(int i=0;i<n;i++,w*=W){
                a[i]=a0[i]+a1[i]*w;
                a[i+n]=a0[i]-a1[i]*w;
        }
}
int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
                cin>>g[i];
                g2[n-i]=g[i];
                f[i]=1.0/(i*i);
        }
        for(m=n,n=1;n<2*m;n*=2);
        FFT(f,n/2,1),FFT(g,n/2,1),FFT(g2,n/2,1);
        for(int i=0;i<n;i++) g[i]*=f[i],g2[i]*=f[i];
        FFT(g,n/2,-1),FFT(g2,n/2,-1);
        for(int i=1;i<=n;i++){
                printf("%.3lf\n",g[i].real()/n-g2[m-i].real()/n);
        }
}

(可能写递归的FFT常数比较大,但是现在连样例都没过/ll)

2023/11/14 17:38
加载中...