比赛 |
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;
}