# BZOJ3527 [Zjoi2014]力（洛谷3338）

## FFT背板题

Posted by yjjr's blog on January 11, 2018

# 题目

$令Ei=Fi/qi，求Ei.$ 输入输出格式 输入格式：

n行，第i行输出Ei。

5 4006373.885184 15375036.435759 1717456.469144 8514941.004912 1410681.345880

-16838672.693 3439.793 7509018.566 4595686.886 10903040.872

# 分析

$A[i]=q[i],B[i]=1/(i^2)$

C[i]已经是标准的卷积形式了，D[i]也可以转换，都用FFT就可以辣

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#define pi acos(-1)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e5+6;
typedef complex<double> E;
int n,m,L;double x;
E f[maxn],ft[maxn],g[maxn],e1[maxn],e2[maxn];
int rev[maxn];

void fft(E *a,int f){
rep(i,0,n-1)if(i>rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1){
E wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=(i<<1)){
E w(1,0);
for(int k=0;k<i;k++,w*=wn){
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
if(f==-1)rep(i,0,n-1)a[i]/=n;
}

int main()
{
rep(i,0,n){
scanf("%lf",&x);
f[i]=x;ft[n-i]=x;
}
rep(i,1,n)g[i]=(1.0/i/i);
for(n=1;n<=m;n<<=1)L++;
rep(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
fft(f,1);fft(g,1);fft(ft,1);
rep(i,0,n-1)e1[i]=f[i]*g[i];
rep(i,0,n-1)e2[i]=ft[i]*g[i];
fft(e1,-1);fft(e2,-1);
rep(i,0,m/2)printf("%.3lf\n",e1[i].real()-e2[m/2-i].real());
return 0;
}