RT,FFT函数照搬之前的模板应该没问题,Complex类也应该没问题。问题大概率出在主函数中。
还有,我输出的结果和样例有相似之处,第一位数都一样,貌似是精度问题?
样例输入:
5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
样例输出:
-16838672.693
3439.793
7509018.566
4595686.886
10903040.872
我的输出:
-16409907.469
59867.047
7509018.566
4435431.931
10037641.047
代码:
#include <bits/stdc++.h>
#define MAXN 300000
const double PI = acos(-1);
class Complex {
public:
inline Complex(double x = 0, double y = 0) : x(x), y(y) {}
inline Complex operator + (const Complex &cp) const { return Complex(this->x + cp.x, this->y + cp.y); }
inline Complex operator - (const Complex &cp) const { return Complex(this->x - cp.x, this->y - cp.y); }
inline Complex operator * (const Complex &cp) const { return Complex(this->x * cp.x - this->y * cp.y, this->x * cp.y + this->y * cp.x); }
double x, y;
} f[MAXN], g[MAXN], f_[MAXN];
int m = 1, rotate[MAXN];
inline int read() {
int num = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
num = num * 10 + ch - '0';
ch = getchar();
}
return num * flag;
}
inline void FFT(Complex *Fc, int flag) {
for (register int i = 0; i < m; i++) if (i < rotate[i]) std::swap(Fc[i], Fc[rotate[i]]);
for (register int num = 2; num <= m; num <<= 1) {
Complex omega_num_flag_one(cos(2 * PI / num), flag * sin(2 * PI / num));
for (register int i = 0; i < m; i += num) {
Complex omega_num_i(1, 0);
for (register int j = i; j < i + (num >> 1); j++) {
Complex right_value = omega_num_i * Fc[j + (num >> 1)];
Fc[j + (num >> 1)] = Fc[j] - right_value;
Fc[j] = Fc[j] + right_value;
omega_num_i = omega_num_i * omega_num_flag_one;
}
}
}
if (flag == -1) for (register int i = 0; i < m; i++) Fc[i].x /= m;
}
int main() {
int n = read();
for (register int i = 1; i <= n; i++) scanf("%lf", &f[i].x), g[i].x = double(1.0 / i / i), f_[n - i].x = f[i].x;
while(m <= n) m <<= 1;
for (register int i = 0; i < m; i++) rotate[i] = (rotate[i >> 1] >> 1) | (i & 1 ? m >> 1 : 0);
FFT(f, 1); FFT(g, 1); FFT(f_, 1);
for (register int i = 0; i < m; i++) f[i] = f[i] * g[i], f_[i] = f_[i] * g[i];
FFT(f, -1); FFT(f_, -1);
for (register int i = 1; i <= n; i++) printf("%.3lf\n", f[i].x - f_[n - i].x);
return 0;
}