题目链接

设\(A[i]=q[i]\),\(B[i]=\frac{1}{i^2}\),\(A\times B\)就能得到第一个\(\sum\)，把\(A\)反过来再\(\times B\)就能得到第二个\(\sum\)，相减即可。

用\(FFT\)算。

#include <cstdio>

#include <cmath>

#include <algorithm>

#define re register

using namespace std;

const int MAXN = 300010;

const double PI = M_PI;

struct complex{

    double x, y;

    complex(double xx = 0, double yy = 0){ x = xx; y = yy; }

}a[MAXN], b[MAXN];

inline complex operator + (complex a, complex b){

	return complex(a.x + b.x, a.y + b.y);

}

inline complex operator - (complex a, complex b){

	return complex(a.x - b.x, a.y - b.y);

}

inline complex operator * (complex a, complex b){

	return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);

}

double q[MAXN], e[MAXN];

int r[MAXN], n, m;

void FFT(complex *f, int mode){

	for(re int i = 0; i < m; ++i) if(i < r[i]) swap(f[i], f[r[i]]);

	for(re int p = 2; p <= m; p <<= 1){

	   re int len = p >> 1;

	   re complex tmp(cos(PI / len), mode * sin(PI / len));

	   for(re int l = 0; l < m; l += p){

	      re complex w(1, 0);

	      for(re int k = l; k < l + len; ++k){

	      	 re complex t = w * f[len + k];

	      	 f[len + k] = f[k] - t;

	      	 f[k] = f[k] + t;

	      	 w = w * tmp;

	      }

	   }

    }

}

int main(){

	scanf("%d", &n);

	for(re int i = 1; i <= n; ++i) scanf("%lf", &q[i]);

	for(re int i = 1; i <= n; ++i) a[i].x = q[i], b[i].x = 1.0 / (1.0 * i * i);

	for(m = 1; m <= (n << 1); m <<= 1);

	for(re int i = 1; i < m; ++i) r[i] = r[i >> 1] >> 1 | ((i & 1) * (m >> 1));

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

	for(re int i = 0; i < m; ++i) a[i] = a[i] * b[i];

	FFT(a, -1);

	for(re int i = 1; i <= n; ++i) e[i] = a[i].x;

	for(re int i = 0; i < m; ++i) a[i].x = b[i].x = a[i].y = b[i].y = 0;

	for(re int i = 1; i <= n; ++i) a[i].x = q[n - i + 1], b[i].x = 1.0 / (1.0 * i * i);

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

	for(re int i = 0; i < m; ++i) a[i] = a[i] * b[i];

	FFT(a, -1);

	for(int i = 1; i <= n; ++i) printf("%.3lf\n", (e[i] - a[n - i + 1].x) / m);

	return 0;

}