问题描述
给出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即可。
样例输入
5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
样例输出
-16838672.693
3439.793
7509018.566
4595686.886
10903040.872
解析
首先，我们先来化简一下式子：
[egin{align}
E[i]=&frac{F[i]}{p[i]}\=&sum_{j<i}{frac{p[j]}{(i-j)^2}}-sum_{j>i}{frac{p[j]}{(i-j)^2}}
end{align}
]
那么，设(f1[i]=p[i],g[i]=frac{1}{i^2})，则原式可以化简得：
[E[i]=sum_{j=1}^{i-1}f1[j]*g[i-j]-sum_{j=i+1}^{n}f1[j]*g[j-i]
]
为了将等式右边的两部分变得形式一样，不妨设(f2[i]=f1[n-i+1])，即将(f1)翻转得到(f2)，就可以达到我们的目的：
[E[i]=sum_{j=1}^{i-1}f1[j]*g[i-j]-sum_{j=1}^{i-1}f2[j]*g[i-j]
]
观察到等式的形式与多项式卷积的形式十分的相似，就是卷积中第(i-1)次方项的系数表达式。因此，我们可以利用FFT分别求出(f1)与(g)、(f2)与(g)的卷积，然后答案即为对应次数项的差。
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 400002
using namespace std;
const double PI=acos(-1);
struct Complex{
double r,i;
}a[N],b[N];
Complex operator + (Complex a,Complex b) {return (Complex){a.r+b.r,a.i+b.i};}
Complex operator - (Complex a,Complex b) {return (Complex){a.r-b.r,a.i-b.i};}
Complex operator * (Complex a,Complex b) {return (Complex){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};}
int n=1,m,i,lim=1,r[N];
double f1[N],f2[N],g[N],ansa[N],ansb[N];
void trans()
{
double tmp[N];
for(int i=m;i>=1;i--) tmp[m-i+1]=f2[i];
for(int i=1;i<=m;i++) f2[i]=tmp[i];
}
void FFT(Complex *a,int inv)
{
for(int i=0;i<n;i++){
if(i<r[i]) swap(a[i],a[r[i]]);
}
for(int l=2;l<=n;l*=2){
int mid=l/2;
Complex omg=(Complex){cos(2*PI/l),inv*sin(2*PI/l)};
for(int i=0;i<n;i+=l){
Complex w=(Complex){1,0};
for(int j=0;j<mid;j++,w=w*omg){
Complex tmp=a[i+j+mid]*w;
a[i+j+mid]=a[i+j]-tmp;
a[i+j]=a[i+j]+tmp;
}
}
}
}
void solve(double *f,double *g,double *ans)
{
for(int i=0;i<n;i++) a[i].r=f[i],a[i].i=0;
for(int i=0;i<n;i++) b[i].r=g[i],b[i].i=0;
FFT(a,1);FFT(b,1);
for(int i=0;i<n;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=1;i<=m;i++) ans[i]=a[i].r/n;
}
int main()
{
cin>>m;
while(n<2*m) n*=2;
while((1<<lim)<n) lim++;
for(i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(lim-1));
for(i=1;i<=m;i++){
cin>>f1[i];
g[i]=1.0/i/i;
f2[i]=f1[i];
}
trans();
solve(f1,g,ansa);
solve(f2,g,ansb);
for(i=1;i<=m;i++) printf("%.3lf
",ansa[i]-ansb[m-i+1]);
return 0;
}