题目链接
题目大意： Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2 ，令Ei=Fi/qi，求Ei
题解：代进去，得到 Ei=∑j=0i−1qj(j−i)2−∑j=i+1n−1qj(j−i)2
设 f[i]=qi,g[i]=1i2 ,其中 g[0]=0
变成 Ei=∑j=0i−1f[j]g[i−j]−∑j=i+1n−1f[j]g[j−i]
左边的是卷积形式，右边的把f翻转一下也是卷积形式……
然后就做完了……
我的收获：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <complex> using namespace std; #define pi acos(-1) typedef complex<double> C; const int N=262145; int n,m,L,R[N]; C f[N],_f[N],g[N],e1[N],e2[N]; void pre() { m=n<<1;for(n=1;n<=m;n<<=1) L++; for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); } void FFT(C *a,int f){ for(int i=0;i<n;i++) if(R[i]>i) swap(a[i],a[R[i]]); for(int i=1;i<n;i<<=1){ C wn(cos(pi/i),f*sin(pi/i)); for(int j=0;j<n;j+=i<<1){ C w(1,0);for(int k=0;k<i;k++,w*=wn){ C x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y;a[j+k+i]=x-y; } } } if(f==-1) for(int i=0;i<n;i++) a[i]/=n; } void work() { FFT(f,1),FFT(g,1),FFT(_f,1); for(int i=0;i<n;i++) e1[i]=f[i]*g[i]; for(int i=0;i<n;i++) e2[i]=_f[i]*g[i]; FFT(e1,-1);FFT(e2,-1); for(int i=0;i<=m/2;i++) printf("%.3lf\n",e1[i].real()-e2[m/2-i].real()); } void init() { scanf("%d",&n);n--; for(int i=0;i<=n;i++) scanf("%lf",&f[i]),_f[n-i]=f[i]; for(int i=1;i<=n;i++) g[i]=(1.0/i/i); pre(); } int main() { init(); work(); return 0; }