事实说明只会FFT板子是没有用的，还要把式子推成能用FFT/转化一下卷积的方式
虽然这个题不算难的多项式卷积
稍微化简一下可以发现实际是$q_i$和$frac{1}{(i-j)^2}$在卷，然后每两项是在向下标差值的那项做贡献，而直接卷是向两项下标和的那项做贡献。于是把前半部分的$frac{1}{(i-j)^2}$做成负的，后半段的做成正的，这样卷完后半段就是题目要求的东西。当然把一个序列反过来再卷也是对的
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=400005,M=30; 7 const double pai=acos(-1); 8 struct cpx 9 { 10 double x,y; 11 }a[N],b[N]; 12 int n,m,nm,rev[N]; 13 double Sin[M],Cos[M]; 14 cpx operator + (cpx a,cpx b) 15 { 16 return (cpx){a.x+b.x,a.y+b.y}; 17 } 18 cpx operator - (cpx a,cpx b) 19 { 20 return (cpx){a.x-b.x,a.y-b.y}; 21 } 22 cpx operator * (cpx a,cpx b) 23 { 24 double x1=a.x,x2=b.x,y1=a.y,y2=b.y; 25 return (cpx){x1*x2-y1*y2,x1*y2+x2*y1}; 26 } 27 int Log2(int len) 28 { 29 return (int)(log(len)/log(2)+0.5); 30 } 31 void prework() 32 { 33 register int i; 34 scanf("%d",&n),nm=n<<1; 35 for(i=0;i<n;i++) scanf("%lf",&a[i].x); 36 for(i=0;i<n-1;i++) b[i].x=(double)-1/(n-i-1)/(n-i-1); 37 for(i=n;i<nm-1;i++) b[i].x=(double)1/(i-n+1)/(i-n+1); 38 m=1; while(m<=nm) m<<=1; 39 for(i=1;i<=24;i++) 40 Sin[i]=sin(2*pai/(1<<i)),Cos[i]=cos(2*pai/(1<<i)); 41 for(i=0;i<m;i++) 42 rev[i]=(rev[i>>1]>>1)+(i&1)*(m>>1); 43 } 44 void transform(cpx *c,int t) 45 { 46 register int i,j,k; 47 for(i=0;i<m;i++) 48 if(rev[i]>i) swap(c[i],c[rev[i]]); 49 for(i=2;i<=m;i<<=1) 50 { 51 int len=i>>1; 52 cpx omg={Cos[Log2(i)],Sin[Log2(i)]*t}; 53 for(j=0;j<m;j+=i) 54 { 55 cpx ori={1,0},tmp; 56 for(k=j;k<j+len;k++) 57 { 58 tmp=ori*c[k+len],ori=ori*omg; 59 c[k+len]=c[k]-tmp,c[k]=c[k]+tmp; 60 } 61 } 62 } 63 } 64 int main() 65 { 66 register int i; 67 prework(),transform(a,1),transform(b,1); 68 for(i=0;i<m;i++) a[i]=a[i]*b[i]; 69 transform(a,-1); 70 for(i=n-1;i<nm-1;i++) printf("%f ",a[i].x/m); 71 return 0; 72 }