调了好长时间但是样例没过qwq
感觉应该是fft的问题,但是我是从模板上拷过来的啊
#include <cstdio>
#include <cmath>
#include <algorithm>
const int N = 150000;
const int PI = acos(-1.0);
struct complex {
// x is real, y is imaginary
double x, y;
complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
complex operator + (const complex &rhs) const {
return complex(x + rhs.x, y + rhs.y);
}
complex operator - (const complex &rhs) const {
return complex(x - rhs.x, y - rhs.y);
}
complex operator * (const complex &rhs) const {
return complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
}
};
int n, m;
int tr[N << 1];
complex a[N << 1], b[N << 1], c[N << 1];
void fft(complex *f, bool flag) {
for (int i = 0; i < n; i++) {
if (i < tr[i]) {
std::swap(f[i], f[tr[i]]);
}
}
for (int p = 2; p <= n; p <<= 1) {
int len = p >> 1;
complex tG(cos(2 * PI / p), sin(2 * PI / p));
if (!flag) {
tG.y *= -1;
}
for (int k = 0; k < n; k += p) {
complex buf(1, 0);
for (int l = k; l < k + len; l++) {
complex tt = buf * f[len + l];
f[len + l] = f[l] - tt;
f[l] = f[l] + tt;
buf = buf * tG;
}
}
}
}
signed main() {
scanf("%d", &n);
m = n;
for (int i = 1; i <= n; i++) {
scanf("%lf", &a[i].x);
b[i].x = 1.0 / (double) i / (double) i;
c[n - i].x = a[i].x;
a[i].y = 0, b[i].y = 0, c[i].y = 0;
}
// for (int i = 1; i <= n; i++) {
// printf("%lf %lf %lf\n", a[i].x, b[i].x, c[i].x);
// }
while (n <= m << 1) {
n <<= 1;
}
for (int i = 0; i < n; i++) {
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
// printf("%d ", tr[i]);
}
fft(a, 1); fft(b, 1); fft(c, 1);
// for(int i=0;i<n;i++){
// printf("%lf %lf\n", a[i].x, a[i].y);
// }
for (int i = 0; i < n; i++) {
a[i] = a[i] * b[i];
c[i] = c[i] * b[i];
}
fft(a, 0); fft(c, 0);
for (int i = 0; i < n; i++) {
a[i].x /= (double) n;
c[i].x /= (double) n;
}
for (int i = 1; i <= m; i++) {
printf("%.3lf\n", a[i].x - c[m - i].x);
}
return 0;
}