[ZJOI2014]力

链接：https://www.luogu.com.cn/problem/P3338 题目描述：~~题目已经说的很清楚了吧。~~ 题解：我们可以知道$E_{j}=\sum_{i=1}^{j-1}\frac{q_{i}}{(j-i)^2}-\sum_{i=j+1}^{n}\frac{q_{i}}{(j-i)^2}$ 容易发现前面是一个卷积的形式，关键看后面： 令$t_{j}=\sum_{i=j+1}^{n}\frac{q_{i}}{(j-i)^2}$ 令$h_{i}=q_{n-i},k_{i}=t_{n-i+1}$ 则$t_{j}=\sum_{i=j+1}^{n}\frac{q_{n-i+1}}{(j-i)^2}$ $t_{j}=\sum_{i=1}^{n-j}\frac{q_{n-i+1}}{(n-j-i+1)^2}$ 则有$k_{j}=t_{n-j}=\sum_{i=1}^{j}\frac{q_{n-i+1}}{(j-i)^2}$ 则$k_{j}=\sum_{i=1}^{j}\frac{k_{i}}{(j-i)^2}$ 容易发现这也是一个卷积的形式，跑$FFT$就行了。 ``` #include #include #include using namespace std; struct complex { double x,y; }; const double Pi=asin(1)*2; complex a[2000001],b[2000001],c[2000001],d[2000001],w,wn; double q[2000001],ans[2000001]; complex make_complex(double a,double b) { complex temp; temp.x=a; temp.y=b; return temp; } complex add(complex a,complex b) { return make_complex(a.x+b.x,a.y+b.y); } complex myminus(complex a,complex b) { return make_complex(a.x-b.x,a.y-b.y); } complex mul(complex a,complex b) { return make_complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y); } void FFT(int limit,complex *s,int type) { if (limit==1) return; complex a2[limit/2+1],b2[limit/2+1]; for (int i=0;i<limit;i+=2) {="" a2[i="" 2]="s[i];" b2[i="" }="" fft(limit="" 2,a2,type);="" 2,b2,type);="" w="make_complex(cos(2*Pi/limit),type*sin(2*Pi/limit));" wn="make_complex(1,0);" for="" (int="" i="0;i<limit/2;++i,wn=mul(w,wn))" s[i]="add(a2[i],mul(wn,b2[i]));" s[i+limit="" return;="" int="" main()="" n,limit="1;" cin="">>n; for (int i=1;i<=n;++i) cin>>q[i]; for (int i=1;i<=n;++i) a[i].x=1.0/i/i; for (int i=1;i<=n;++i) b[i].x=q[i]; while (limit<=2*n) limit*=2; FFT(limit,a,1); FFT(limit,b,1); for (int i=0;i<=limit;++i) c[i]=mul(a[i],b[i]); FFT(limit,c,-1); for (int i=1;i<=n;++i) ans[i]=c[i].x/limit; for (int i=1;i<=n;++i) d[i].x=q[n-i+1]; FFT(limit,d,1); for (int i=0;i<=limit;++i) c[i]=mul(a[i],d[i]); FFT(limit,c,-1); for (int i=1;i<=n;++i) ans[i]-=c[n-i+1].x/limit; for (int i=1;i<=n;++i) printf("%0.3lf\n",ans[i]); return 0; }