题目链接：bzoj3527 题目大意： 给出n个数qi，定义Fj: Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2 令 Ei=Fiqi 。求 Ei 。
题解： FFT 代入可得
Ei=∑j<iqiqj(i−j)2−∑j>iqiqj(i−j)2qi=∑j<iqj(i−j)2−∑j>iqj(i−j)2 设 f(i)=1i2，1≤i≤n 。 所以 Ei=∑j<iqj×f(i−j)−∑j>iqj×f(i−j) 卷积啊卷积的形式啊。 把 f(i) 在 [−n,n] 范围内的值都求出来就直接 E=q∗f 了 可以发现 i<0 时 f(i)=−1i2 ； i=0 时 f(i)=0 ； i>0 时 f(i)=1i2 。 把下标都+n弄成正的，然后就套FFT。 答案就是[n,n+n]那部分的。 #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define maxn 800010 const double pi=acos(-1); struct Complex { double x,y; Complex(){x=y=0;} Complex(double x,double y):x(x),y(y){} friend inline Complex operator + (Complex x,Complex y){return Complex(x.x+y.x,x.y+y.y);} friend inline Complex operator - (Complex x,Complex y){return Complex(x.x-y.x,x.y-y.y);} friend inline Complex operator * (Complex x,Complex y){return Complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);} }q[maxn],f[maxn]; void DFT(Complex *c,int ln,int t) { for(int i=0,j=0;i<ln;i++) { if(i>j) swap(c[i],c[j]); for(int k=ln>>1;(j^=k)<k;k>>=1); } for (int i=1;(1<<i)<=ln;i++) { int m=(1<<i); Complex wn(cos(2*pi/m),t*sin(2*pi/m)); for (int k=0;k<ln;k+=m) { Complex w(1,0); for (int j=0;j<(m>>1);j++,w=w*wn) { Complex a0=c[k+j]; Complex a1=w*c[k+j+(m>>1)]; c[k+j]=a0+a1; c[k+j+(m>>1)]=a0-a1; } } } } double ans[maxn]; void FFT(int ln) { int fn=1;while (fn<=ln) fn<<=1; DFT(q,fn,1);DFT(f,fn,1); for (int i=0;i<=fn;i++) q[i]=q[i]*f[i]; DFT(q,fn,-1); for (int i=0;i<=ln;i++) ans[i]=q[i].x/fn; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int n,m,i; scanf("%d",&n);n--; for (i=0;i<=n;i++) scanf("%lf",&q[i].x); m=2*n;f[n].x=0; for (i=1;i<=n;i++) f[i+n].x=(double)1/i/i,f[-i+n].x=-(double)1/i/i; FFT(n+m); for (i=n;i<=n+n;i++) printf("%.3lf\n",ans[i]); return 0; }