为了简化问题，我们定义辅助函数：

• 令 $f[i] = q_i$（多项式的系数）
• 令 $g[i] = \frac{1}{i^2}$（注意 $g[0] = 0$）

这样，$E_j$ 可以拆解为两部分：

1. 第一部分：$A_j = \sum_{i=1}^{j-1} f[i] \cdot g[j-i]$，这已经是一个标准的卷积形式。
2. 第二部分：$B_j = \sum_{i=j+1}^{n} f[i] \cdot g[i-j]$，需要通过数组翻转将其转化为卷积形式。

🧠 卷积处理与数组翻转

处理第二部分 $B_j$ 的技巧：

1. 构造一个翻转数组 $f'[i] = f[n-i+1]$。
2. 通过变量代换（令 $t = n - j$），可以将 $B_j$ 转化为：$$B_j = \sum_{i=0}^{t} f'[t-i] \cdot g[i]$$ 这同样是一个卷积形式。

因此，整个计算过程可以归纳为：

1. 计算卷积 $A = f * g$。
2. 计算卷积 $B = f' * g$。
3. 对于每个 $j$，$E_j = A_j - B_{n-j}$。

⚠️ 计算精度提醒

在计算 $g[i] = \frac{1}{i^2}$ 时，务必注意计算方式。推荐使用 1.0 / i / i，而不是 1.0 / (i * i)，因为当 i 较大时，i * i 可能导致整数溢出或精度损失。

🧮 FFT 代码实现

以下是基于 FFT 的 C++ 实现。代码中包含了复数类、FFT 变换以及如何组织多项式系数来计算卷积。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1 << 18; // 选择2的幂次，大于2*n
const double PI = acos(-1.0);

struct Complex {
    double r, i;
    Complex(double r = 0.0, double i = 0.0) : r(r), i(i) {}
    Complex operator + (const Complex &rhs) const { return Complex(r + rhs.r, i + rhs.i); }
    Complex operator - (const Complex &rhs) const { return Complex(r - rhs.r, i - rhs.i); }
    Complex operator * (const Complex &rhs) const {
        return Complex(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r);
    }
};

void FFT(Complex a[], int len, int inv) {
    for (int i = 0, j = 0; i < len; i++) {
        if (i > j) swap(a[i], a[j]);
        for (int k = len >> 1; (j ^= k) < k; k >>= 1);
    }
    for (int h = 2; h <= len; h <<= 1) {
        Complex wn(cos(inv * 2 * PI / h), sin(inv * 2 * PI / h));
        for (int j = 0; j < len; j += h) {
            Complex w(1, 0);
            for (int k = j; k < j + h / 2; k++) {
                Complex u = a[k];
                Complex t = w * a[k + h / 2];
                a[k] = u + t;
                a[k + h / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if (inv == -1) {
        for (int i = 0; i < len; i++) a[i].r /= len;
    }
}

int n;
double q[MAXN];
Complex f[MAXN], g[MAXN], f_rev[MAXN], A[MAXN], B[MAXN];

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

    int len = 1;
    while (len < 2 * n + 1) len <<= 1; // 确定扩展长度

    // 构建多项式 f 和 g
    for (int i = 1; i <= n; i++) {
        f[i].r = q[i];
        if (i > 0) {
            g[i].r = 1.0 / i / i; // 注意计算方式
        }
    }

    // 计算第一部分卷积 A = f * g
    FFT(f, len, 1);
    FFT(g, len, 1);
    for (int i = 0; i < len; i++) A[i] = f[i] * g[i];
    FFT(A, len, -1);

    // 构建翻转多项式 f_rev
    for (int i = 0; i < len; i++) f_rev[i] = Complex(0, 0);
    for (int i = 1; i <= n; i++) {
        f_rev[n - i + 1].r = q[i];
    }

    // 计算第二部分卷积 B = f_rev * g
    FFT(f_rev, len, 1);
    for (int i = 0; i < len; i++) B[i] = f_rev[i] * g[i];
    FFT(B, len, -1);

    // 输出结果 E_j = A[j] - B[n - j + 1]
    for (int i = 1; i <= n; i++) {
        double ans = A[i].r - B[n - i + 1].r;
        printf("%.3f\n", ans);
    }

    return 0;
}

💡 核心思路与技巧总结

1. 卷积识别：识别出题目中的求和式可以转化为多项式卷积是解题的关键一步。
2. 数组翻转：对于涉及负索引或反向索引的求和，数组翻转是一个常用的转化技巧。
3. FFT应用：FFT能高效计算多项式卷积，将时间复杂度从 $O(n^2)$ 降为 $O(n \log n)$。
4. 精度处理：在数值计算中，注意运算顺序和数据类型，防止溢出和精度损失。