题目链接：点我啊╭(╯^╰)╮
题目大意：
解题思路：
E
i
=
F
i
q
i
=
∑
j
=
1
i
−
1
q
j
(
i
−
j
)
2
−
∑
j
=
i
+
1
n
q
j
(
i
−
j
)
2
E_i=\frac{F_i}{q_i} = \sum_{j=1}^{i-1} \frac{q_j}{(i-j)^2} - \sum_{j=i+1}^{n} \frac{q_j}{(i-j)^2}
Ei=qiFi=∑j=1i−1(i−j)2qj−∑j=i+1n(i−j)2qj
令
f
i
=
q
i
f_i=q_i
fi=qi，
g
i
=
1
i
2
g_i=\frac{1}{i^2}
gi=i21，
p
i
=
q
n
−
i
+
1
p_i=q_{n-i+1}
pi=qn−i+1
E
i
=
∑
j
=
1
i
−
1
f
j
g
i
−
j
−
∑
j
=
i
+
1
n
q
j
g
i
−
j
=
∑
j
=
1
i
−
1
f
j
g
i
−
j
−
∑
j
=
1
i
−
1
p
j
g
j
−
i
E_i = \sum_{j=1}^{i-1} f_j g_{i-j} - \sum_{j=i+1}^{n} q_{j} g_{i-j} = \sum_{j=1}^{i-1} f_j g_{i-j} - \sum_{j=1}^{i-1} p_{j} g_{j-i}
Ei=∑j=1i−1fjgi−j−∑j=i+1nqjgi−j=∑j=1i−1fjgi−j−∑j=1i−1pjgj−i
两边都是卷积的形式，FFT即可
核心：卷积形式的变换
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const double pi = acos(-1);
int n, len, rev[maxn<<1];
struct cp {
double x, y;
cp(double _x=0, double _y=0) {x = _x, y = _y;}
cp operator + (const cp &A) const {return cp(x+A.x, y+A.y);}
cp operator - (const cp &A) const {return cp(x-A.x, y-A.y);}
cp operator * (const cp &A) const {return cp(x*A.x-y*A.y, x*A.y+y*A.x);}
} f[maxn<<1], p[maxn<<1], g[maxn<<1];
void fft(cp *f, int inv) {
for(int i=0; i<len; i++) if(i<rev[i]) swap(f[i], f[rev[i]]);
for(int p=2; p<=len; p<<=1) { // 区间长度
int Len = p >> 1; // 待合并长度
cp wn(cos(2*pi/p), inv*sin(2*pi/p));
for(int k=0; k<len; k+=p) { // 起始点
cp w(1, 0);
for(int i=k; i<k+Len; i++) {
cp tmp = w * f[i+Len];
f[i+Len] = f[i] - tmp;
f[i] = f[i] + tmp;
w = w * wn;
}
}
}
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%lf", &f[i].x);
p[i].x = f[i].x;
g[i].x = 1.0 / double(i) / double(i);
}
reverse(p+1, p+1+n);
for(len=1; len<=n+n; len<<=1);
for(int i=0; i<len; i++) rev[i] = (rev[i>>1]>>1) | ((i&1) ? len>>1 : 0);
fft(f, 1), fft(p, 1), fft(g, 1);
for(int i=0; i<len; i++) f[i] = f[i] * g[i], p[i] = p[i] * g[i];
fft(f, -1), fft(p, -1);
for(int i=1; i<=n; i++) f[i].x /= len, p[i].x /= len;
for(int i=1; i<=n; i++) printf("%.3f\n", f[i].x - p[n-i+1].x);
}
