FFT求调,没过样例(认真回皆关)
查看原帖
FFT求调,没过样例(认真回皆关)
373905
HappyJaPhy楼主2024/2/28 21:04

貌似剪切板用不了了,在这里将就看一下吧。

#include <bits/stdc++.h>
#define int long long
#define N 400005
const double PI = acos(-1.0);
using namespace std;
int n, rev[N];
complex<double> a[N], b[N], c[N];

inline void FFT(complex<double> *A, int n) {
	for (int i = 1; i <= n; i++) {
		if (i < rev[i]) swap(A[i], A[rev[i]]);
	}
	for (int m = 1, len = 2; len <= n; m = len, len <<= 1) {
		complex<double> wn(cos(PI / m), sin(PI / m)), w(1, 0);
		for (int L = 0, R = len - 1; R <= n; L += len, R += len) {
			auto w0 = w;
			for (int p = L; p < L + m; p++) {
				auto x = A[p], y = w0 * A[p + m];
				A[p] = x + y, A[p + m] = x - y;
				w0 *= wn;
			}
		}
	}
}

signed main() {
	scanf("%lld", &n);
	double re;
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &re);
		c[i] = a[i] = re;
		b[i] = (double)(1.0 / i / i);
	}
	reverse(c + 1, c + 1 + n);
	int x = 1, l = -1;
	while (x <= (n << 1)) x <<= 1, l++;
	for (int i = 1; i <= x; i++) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l);
	}
	FFT(a, x), FFT(b, x), FFT(c, x);
	for (int i = 0; i < x; i++) {
		a[i] = b[i] * b[i];
		c[i] = c[i] * b[i];
	}
	FFT(a, x), FFT(c, x);
	reverse(a + 1, a + x), reverse(c + 1, c + x);
	for (int i = 1; i <= n; i++) {
		printf("%.3lf\n", (a[i].real() - c[n - i + 1].real()) / x);
	}
	return 0;
}

连样例都没过,但是样例的第一个输出是对的,后面都是错的。

2024/2/28 21:04
加载中...