洛谷 P3338 [ZJOI2014]力

题意简述

读入\(n\)个数\(q_i\)

设\(F_j = \sum\limits_{ij}\frac{q_i\times q_j}{(i-j)^2 }\)
令\(E_i=\frac{F_i}{q_i}\)，求\(E_i\)

题解思路

先推式子

\(E_j=\frac{F_j}{q_j}=\sum\limits_{ij}\frac{q_i}{(i-j)^2 }\)

设\(T_i=i^{-2}\)

则\(E_j=\sum\limits_{i=1}^{j-1}q_iT_{j-i}-\sum\limits_{i=j+1}^{n}q_iT_{i-j}\)

再设\(p_i=q_{n-i+1}\)

则\(E_j=\sum\limits_{i=1}^{j-1}q_iT_{j-i}-\sum\limits_{i=1}^{j-1}p_iT_{j-i}\)

可以发现，这两项都是两个多项式卷积的结果，所以可以用FFT来做

注意：如果用三次变两次优化，会掉精

代码

#include 
#include 
#include 
const int N=400005;
const double Pi=acos(-1.0);
int n,nn,m,lim=1,l=-1,r[N];
struct Com {
	long double x,y;
	Com(long double xx=0,long double yy=0) { x=xx; y=yy; }
}p[N],q[N],t[N];
Com operator +(const Com& x,const Com& y) { return Com(x.x+y.x,x.y+y.y); }
Com operator -(const Com& x,const Com& y) { return Com(x.x-y.x,x.y-y.y); }
Com operator *(const Com& x,const Com& y) { return Com(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x); }
inline void FFT(Com *x,const int& lim,const int& type) {
	for (register int i=0;i>n;
	for (register int i=1;i<=n;++i) std::cin>>p[i].x,t[i].x=1.0/i/i;
	for (register int i=1;i<=n;++i) q[i].x=p[n-i+1].x;
	for (nn=n<<1;lim<=nn;lim<<=1,++l);
	for (register int i=0;i>1]>>1)|((i&1)<