比赛 2022级数学专题练习赛6 评测结果 AAAAAAAAAA
题目名称 最终得分 100
用户昵称 op_组撒头屯 运行时间 4.304 s
代码语言 C++ 内存使用 50.21 MiB
提交时间 2023-01-23 21:13:12
显示代码纯文本
//因为一个弱智错误水题调了一晚上,哈哈 ^_^ 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(CP)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(CP)*(n))
const int N=(1<<18)+5;
const ld pi=acos(-1);
struct CP{
    ld a,b;
    CP operator+(const CP&x)const{
        return {x.a+a,x.b+b};
    }
    CP operator-(const CP&x)const{
        return {a-x.a,b-x.b};
    }
    CP operator*(const CP&x)const{
        return {a*x.a-b*x.b,a*x.b+b*x.a};
    }
}a[N<<1],b[N<<1];
ld r[N<<1],ans[N<<1],tot;
int n,m;
int tr[N<<1];
void FFT(CP *g,bool opt){
    static CP f[N<<1];clr(f,n);
    for (int i=0;i<n;i++)f[i]=g[tr[i]];
    for (int p=2;p<=n;p<<=1){
        int len=p>>1;
        CP w0={cos(pi*2/p),sin(pi*2/p)};
        if (opt)w0.b*=-1;
        for (int i=0;i<n;i+=p){
            CP w={1,0};
            for (int j=i;j<i+len;j++){
                CP now=w*f[j+len];
                f[j+len]=f[j]-now;
                f[j]=f[j]+now;
                w=w*w0;
            }
        }
    }
    for (int i=0;i<n;i++)g[i]=f[i];
    
}
void solve(bool opt){
    clr(a,n);clr(b,n);
    for (int i=0;i<m;i++){
        a[i]={r[i],0};
        b[i]={i?(ld)1.0/i/i:0,0};
    }
    FFT(a,0);FFT(b,0);
    for (int i=0;i<n;i++)a[i]=a[i]*b[i];
    FFT(a,1);
    if (opt)for (int i=0;i<m;i++)ans[m-1-i]-=a[i].a/n;
    else for (int i=0;i<m;i++)ans[i]+=a[i].a/n;
}
int main(){
	freopen ("force.in","r",stdin);
	freopen ("force.out","w",stdout);
	scanf("%d",&n);
	for (m=n,n=1;n<=m+m;n<<=1);
	for (int i=0;i<n;i++){
	    tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    }
	for (int i=0;i<m;i++)scanf("%Lf",&r[i]);
	solve(0);
	reverse(r,r+m);
	solve(1);
	for(int i=0;i<m;i++)printf("%.4Lf\n",ans[i]);
	return 0;
}