1 条题解
-
0
C++ :
#include <cstdio> #include <algorithm> #include <complex> using namespace std; typedef complex<double> Complex; #define LL long long const int MAXN = 1 << 18; const double PI = acos(-1.0); void FFT(Complex P[], int n, int oper) { for (int i = 1, j = 0; i < n - 1; i++) { for (int s = n; j ^= s >>= 1, ~j & s;); if (i < j) swap(P[i], P[j]); } Complex unit_p0; for (int d = 0; (1 << d) < n; d++) { int m = 1 << d, m2 = m * 2; double p0 = PI / m * oper; unit_p0 = Complex(cos(p0), sin(p0)); for (int i = 0; i < n; i += m2) { Complex unit = 1; for (int j = 0; j < m; j++) { Complex &P1 = P[i + j + m], &P2 = P[i + j]; Complex t = unit * P1; P1 = P2 - t; P2 = P2 + t; unit = unit * unit_p0; } } } } int n; Complex x[MAXN], y[MAXN], z[MAXN], c[MAXN]; inline double squ(double k) { return k * k; } int main() { //freopen("force.in", "r", stdin); //freopen("force.out", "w", stdout); scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf", &x[i]); for (int i = 0; i < n; i++) y[i] = -1.0 / squ(n - i); y[n] = 0; for (int i = n + 1; i <= 2 * n; i++) y[i] = 1.0 / squ(i - n); int MXN = 1; while (MXN < n * 2 + 1) MXN *= 2; //printf("%d\n", MXN); for (int i = n; i < MXN; i++) x[i] = 0; for (int i = 2 * n + 1; i < MXN; i++) y[i] = 0; FFT(x, MXN, 1); FFT(y, MXN, 1); for (int i = 0; i < MXN; ++i) z[i] = x[i] * y[i]; FFT(z, MXN, -1); for (int i = 0; i < MXN; ++i) c[i] = z[i].real() / MXN; for (int i = 0; i < n; i++) printf("%.3f\n", c[n + i].real()); return 0; }
- 1
信息
- ID
- 3722
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者