P3338 [ZJOI2014]力（FFT）

题意：

给定n个实数$q_i$，给出$F_j$的定义如下： $F_j={\sum }_{i<j}\frac{q_i{q}_j}{(i-j{)}^2}-{\sum }_{i>j}\frac{q_i{q}_j}{(i-j{)}^2}$ 令$E_j=\frac{F_j}{q_j}$，求所有$E_j$

要求答案误差不超过10^-2

数据范围：n<=1e5，0<=q(i)<=1e9

解法：

$F_j={\sum }_{i<j}\frac{q_i{q}_j}{(i-j{)}^2}-{\sum }_{i>j}\frac{q_i{q}_j}{(i-j{)}^2}$

$E_j=\frac{F_j}{q_j}$

$消掉q_j得:$

$E_j={\sum }_{i<j}\frac{q_i}{(i-j{)}^2}-{\sum }_{i>j}\frac{q_i}{(i-j{)}^2}$

–

$令f(i)=q_i,g(i)=\frac{1}{i^2},那么式子变为:$

$E_j={\sum }_{i=1}^{j-1}f(i)\ast g(i-j)-{\sum }_{i=j+1}^{n}f(i)\ast g(i-j)$

–

$因为当i在[1,j-1]范围内时,i-j<0,此时g(i-j)=g(j-i),那么式子变为:$

$E_j={\sum }_{i=1}^{j-1}f(i)\ast g(j-i)-{\sum }_{i=j+1}^{n}f(i)\ast g(i-j)$

–

$左边{\sum }_{i=1}^{j-1}f(i)\ast g(j-i)部分是卷积形式,用FFT计算$

$右边{\sum }_{i=j+1}^{n}f(i)\ast g(i-j)可以通过翻转q[]数组变为:{\sum }_{i=1}^{j-1}{f}^{\prime }(i)\ast g(j-i),就变成卷积了$ $计算答案的时候别忘了再翻转一次翻回来$

code：

#include<bits/stdc++.h> using namespace std; const double P=acos(-1.0); struct CC{//复数 double x,y; CC(double xx=0,double yy=0){x=xx,y=yy;} CC operator+(const CC &a)const{return CC(x+a.x,y+a.y);} CC operator-(const CC &a)const{return CC(x-a.x,y-a.y);} CC operator*(const CC &a)const{return CC(x*a.x-y*a.y,x*a.y+y*a.x);} }; void change(CC y[],int len){ for(int i=1,j=len/2;i<len-1;i++){ if(i<j)swap(y[i],y[j]); int k=len/2; while(j>=k){ j-=k; k/=2; } if(j<k)j+=k; } } void fft(CC y[],int len,int on){//on为1或者-1,-1的时候表示逆变换 change(y,len); for(int h=2;h<=len;h<<=1){ CC wn(cos(-on*2*P/h),sin(-on*2*P/h)); for(int j=0;j<len;j+=h){ CC w(1,0); for(int k=j;k<j+h/2;k++){ CC u=y[k]; CC t=w*y[k+h/2]; y[k]=u+t; y[k+h/2]=u-t; w=w*wn; } } } if(on==-1){ for(int i=0;i<len;i++){ y[i].x/=len; } } } // const int maxm=4e5+5; CC f[maxm],ff[maxm],g[maxm]; double q[maxm],qq[maxm]; double ans[maxm]; int n; signed main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf",&q[i]); qq[n-i+1]=q[i]; } int len=1; while(len<n*2)len<<=1; for(int i=1;i<=n;i++){ f[i]=CC(q[i],0); ff[i]=CC(qq[i],0); g[i]=CC(1.0/i/i,0); } for(int i=n+1;i<len;i++){ f[i]=ff[i]=g[i]=CC(0,0); } fft(f,len,1); fft(ff,len,1); fft(g,len,1); for(int i=0;i<=len;i++){ f[i]=f[i]*g[i]; ff[i]=ff[i]*g[i]; } fft(f,len,-1); fft(ff,len,-1); for(int i=1;i<=n;i++){ ans[i]=f[i].x-ff[n-i+1].x; } for(int i=1;i<=n;i++){ printf("%.10f\n",ans[i]); } return 0; }

---