标签：FFT
题目
题目描述
给出n个数qi，给出Fj的定义如下： \(F_j = \sum_{i<j} \frac{q_i q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_i q_j}{(i-j)^2 }\)
\(令Ei=Fi/qi，求Ei.\) 输入输出格式 输入格式：
第一行一个整数n。
接下来n行每行输入一个数，第i行表示qi。
输出格式：
n行，第i行输出Ei。
与标准答案误差不超过1e-2即可。
输入输出样例 输入样例#1： 复制
5 4006373.885184 15375036.435759 1717456.469144 8514941.004912 1410681.345880
输出样例#1： 复制
-16838672.693 3439.793 7509018.566 4595686.886 10903040.872
说明
对于30%的数据，n≤1000。
对于50%的数据，n≤60000。
对于100%的数据，n≤100000，0 < qi<1000000000。
分析
注意：本题卡精度且数组需要开大
设\(A[i]=q[i],B[i]=1/(i^2)\)
\[C[i]=\sum(A[j]*B[i-j]),D[i]=\sum(A[n-j-1]*B[i-j])\]那么\(ans=E[i]=C[i]-D[i]\)
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;
inline ll read()
{
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()
{
n=read();n--;m=2*n;
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;
}
