Description:

给出 $n$ 个数 $q_i$ ，求 $\begin{align}E_j=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i}{(i-j)^2}\end{align}$

Solution:

设 $f[i]=q_i,g[i]=\frac{1}{i^2}$

$\begin{align}E_j=\sum_{i=0}^{j-1}f[i]g[j-i]-\sum_{i=j+1}^{n}f[i]g[j-i]\end{align}$

$\begin{align}=\sum_{i=0}^{j-1}f[i]g[j-i]-\sum_{i=0}^{j-1}f[n-i+1]g[j-i]\end{align}$

是两个卷积的和。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

const double PI = acos(-1);

int n;

#define MAXN 400010

struct complex

{

	double r,i;

	complex(double _r = 0.0,double _i = 0.0){r = _r;i = _i;}

}a[MAXN],b[MAXN],g[MAXN];

complex operator + (complex a,complex b){return complex(a.r + b.r,a.i + b.i);}

complex operator - (complex a,complex b){return complex(a.r - b.r,a.i - b.i);}

complex operator * (complex a,complex b){return complex(a.r * b.r - a.i * b.i,a.i * b.r + a.r * b.i);}

int rev[MAXN];

void FFT(complex *f,int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		complex wn(cos(-type * 2 * PI / i),sin(-type * 2 * PI / i));

		for(int j = 0;j < l;j += i)

		{

			complex w(1,0);

			for(int k = j;k < j + i / 2;++k)

			{

				complex u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)

		{

			f[i].r /= l;

		}

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 0;i < n;++i)scanf("%lf",&a[i].r);

	for(int i = 1;i < n;++i)g[i].r = 1.0 / i / i;

	for(int i = 0;i < n;++i)b[i].r = a[n - i - 1].r;

	int len,l;

	for(len = 1,l = 0;len <= 2 * n;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (l - 1)));

	FFT(g,len,1);FFT(a,len,1);FFT(b,len,1);

	for(int i = 0;i < len;++i)a[i] = a[i] * g[i];

	for(int i = 0;i < len;++i)b[i] = b[i] * g[i];

	FFT(a,len,-1);FFT(b,len,-1);

	for(int i = 0;i < n;++i)

	{

		printf("%.3f\n",a[i].r - b[n - i - 1].r);

	}

	return 0;

}