P3338 [ZJOI2014]力

$$F_j=\sum_{i=1}^{j-1} \frac{q_i \times q_j}{(i-j)^2}-\sum_{i=j+1}^{n} \frac{q_i \times q_j}{(i-j)^2}\\ E_i=\frac{F_i}{q_i}$$ $$F_j=\sum_{i=1}^{j-1} \frac{ q_j}{(i-j)^2}-\sum_{i=j+1}^{n} \frac{q_j}{(i-j)^2}\\$$

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

$$F_j=\sum_{i=1}^{j} f[i]g[j-i]-\sum_{i=j+1}^{n} f[i]g[i-j]\\$$

前面一项取$g[0]=0$，后一项$t=i-j$

$$\sum_{i=j}^{n} f[j]g[i-j]=\sum_{t=0}^{n-j} f[j+t]g[t]=\sum_{t=0}^{n-j} ff[n-j-t+1]g[t]$$

取$ff[0]=0,ff[0]=0$

$$F_j=\sum_{i=0}^{j} f[i]g[j-i]-\sum_{t=0}^{n-j+1} ff[n-j-t+1]g[t]\\$$

$FFT$处理卷积

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

struct Complex
{
    double x, y;
    Complex(double _x = 0.0, double _y = 0.0)
    {
        x = _x;
        y = _y;
    }

    Complex operator-(const Complex &b) const
    {
        return Complex(x - b.x, y - b.y);
    }

    Complex operator+(const Complex &b) const
    {
        return Complex(x + b.x, y + b.y);
    }

    Complex operator*(const Complex &b) const
    {
        return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
    }
};
int rev[N];
void FFT(Complex *A, int n, int inv)
{
    for (int i = 0; i < n; i++)
        if (i < rev[i])
            swap(A[i], A[rev[i]]);
    for (int l = 1; l < n; l <<= 1)
    {
        Complex temp(cos(pi / l), inv * sin(pi / l));
        for (int i = 0; i < n; i += (l << 1))
        {
            Complex omega(1, 0);
            for (int j = 0; j < l; j++, omega = omega * temp)
            {
                Complex x = A[i + j], y = omega * A[i + j + l];
                A[i + j] = x + y;
                A[i + j + l] = x - y;
            }
        }
    }

    if (inv == -1)
        for (int i = 0; i < n; i++)
            A[i].x /= n;
}

void FFTX(Complex *a, int n, Complex *b, int m, Complex *ans)
{
    int ML = 1, bit = 0;
    while (ML < n + m)
        ML <<= 1, bit++;
    for (int i = 0; i < ML; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    FFT(a, ML, 1);
    FFT(b, ML, 1);
    for (int i = 0; i < ML; i++)
        ans[i] = a[i] * b[i];
    FFT(ans, ML, -1);
}
Complex f[N], ff[N], g[N], gg[N];
Complex ans1[N];
Complex ans2[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &f[i].x);
    for (int i = 1; i <= n; i++)
        ff[n - i + 1].x = f[i].x, g[i].x = gg[i].x = (double)(1.0 / i / i);

    FFTX(g, n, f, n, ans1);

    FFTX(gg, n, ff, n, ans2);

    for (int i = 1; i <= n; ++i)
        printf("%.3lf\n", ans1[i].x - ans2[n - i + 1].x);
}