P3338 [ZJOI2014]力 /// FFT 公式转化翻转

题目大意:

https://www.luogu.org/problemnew/show/P3338

题解

P3338 [ZJOI2014]力 /// FFT 公式转化翻转

#include <bits/stdc++.h>
#define N 300005
#define PI acos(-1.0)
using namespace std; struct cpx {
double x,y;
cpx (double a=0.0,double b=0.0) { x=a; y=b; }
cpx operator - (const cpx &b)const { return cpx(x-b.x, y-b.y); }
cpx operator + (const cpx &b)const { return cpx(x+b.x, y+b.y); }
cpx operator * (const cpx &b)const { return cpx(x*b.x-y*b.y, x*b.y+y*b.x); }
}f1[N], f2[N], g[N];
int n, l, len, r[N]; void fft(cpx a[],double on)
{
for(int i=;i<len;i++)
if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=;i<len;i<<=) {
cpx wn(cos(PI/i),on*sin(PI/i));
for(int j=;j<len;j+=(i<<)) {
cpx w(,);
for(int k=;k<i;k++,w=w*wn) {
cpx u=a[j+k], v=w*a[j+k+i];
a[j+k]=u+v, a[j+k+i]=u-v;
}
}
}
} void solve()
{
fft(f1,); fft(f2,); fft(g,);
for(int i=;i<=len;i++)
f1[i]=f1[i]*g[i], f2[i]=f2[i]*g[i];
fft(f1,-); fft(f2,-);
for(int i=;i<=len;i++)
f1[i].x=f1[i].x/len, f2[i].x=f2[i].x/len;
for(int i=;i<=n;i++)
printf("%.3f\n",-f2[n+-i].x+f1[i].x);
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%lf",&f1[i].x);
f2[n+-i].x=f1[i].x;
g[i].x=(double)(1.0/i/i);
} len=; l=;
while(len<(n<<)) len<<=, l++;
for(int i=;i<=len;i++)
r[i]=( r[i>>]>> )|( (i&)<<(l-) ); solve(); return ;
}
上一篇:java词频统计——改进后的单元测试


下一篇:mysql-8.0.11-winx64.zip安装教程