BZOJ 3527 [Zjoi2014]力

题目大意

求$E_i = \sum\limits_{j<i}\frac{q_j}{(i-j)^2}-\sum\limits_{j>i}\frac{q_j}{(i-j)^2}.$

$$\sum\limits_{j<i}\frac{q_j}{(i-j)^2} = \sum\limits_{j=1}^{i}q_j \times \frac{1}{(i-j)^2}$$

第一部分和为$i$直接上FFT就可以解决了。

第二部分难度较大。

$$\sum\limits_{j>i}\frac{q_j}{(i-j)^2} = \sum\limits_{j=1}^{n-i}q_{i+j} \times \frac{1}{j^2}$$

第二部分差为$i$，掉转后上FFT就能解决第二部分了。

作差即可。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double pi=acos(-1);
struct cp
{
	double x,y;
	cp(){x=y=0;}
	cp(double _x,double _y){x=_x,y=_y;}
	cp operator+(const cp &tg){return cp(x+tg.x,y+tg.y);}
	cp operator-(const cp &tg){return cp(x-tg.x,y-tg.y);}
	cp operator*(const cp &tg){return cp(x*tg.x-y*tg.y,x*tg.y+y*tg.x);}
}a[300000],b[300000],c[300000],d[300000];
int n,len=1;
double q[200000];
void fft(cp *x,int flg)
{
	for(int j,k=0,i=0;i<len;++i)
	{
		if(i>k) swap(x[i],x[k]);
		for(j=(len>>1);(k^=j)<j;j>>=1);
	}
	for(int i,j,k=2;k<=len;k<<=1)
	{
		cp wn(cos(2*pi*flg/k),sin(2*pi*flg/k));
		for(i=0;i<len;i+=k)
		{
			cp t,w(1,0);
			for(j=0;j<(k>>1);++j)
			{
				t=w*x[i+j+(k>>1)];
				x[i+j+(k>>1)]=x[i+j]-t;
				x[i+j]=x[i+j]+t;
				w=w*wn;
			}
		}
	}
	if(flg==-1) for(int i=0;i<len;++i) x[i].x/=len;
}
int main()
{
	scanf("%d",&n);
	while(len<=(n<<1)) len<<=1;
	for(int i=1;i<=n;++i) scanf("%lf",q+i);
	for(int i=1;i<=n;++i) a[i]=cp(q[i],0),b[i]=cp(1.0/i/i,0);
	fft(a,1),fft(b,1);
	for(int i=0;i<len;++i) c[i]=a[i]*b[i];
	fft(c,-1);
	a[0]=b[0]=cp();
	for(int i=1;i<=n;++i) a[i]=cp(q[n-i+1],0),b[i]=cp(1.0/i/i,0);
	for(int i=n+1;i<len;++i) a[i]=b[i]=cp();
	fft(a,1),fft(b,1);
	for(int i=0;i<len;++i) d[i]=a[i]*b[i];
	fft(d,-1);
	for(int i=1;i<=n;++i) printf("%lf\n",c[i].x-d[n-i+1].x);
}