【BZOJ 3527】【ZJOI 2014】力

时间：2023-03-08 23:31:15
【BZOJ 3527】【ZJOI 2014】力

代换一下变成多项式卷积，这里是的答案是两个卷积相减，FFT求一下两个卷积就可以啦

详细的题解：http://www.cnblogs.com/iwtwiioi/p/4126284.html

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 500003;

const double Pi = acos(- 1.0);

struct cp {

	double r, i;

	cp (double _r = 0.0, double _i = 0.0) : r(_r), i(_i) {}

	cp operator + (const cp &x) const {return cp(r + x.r, i + x.i);}

	cp operator - (const cp &x) const {return cp(r - x.r, i - x.i);}

	cp operator * (const cp &x) const {return cp(r * x.r - i * x.i, r * x.i + i * x.r);}

};

int rev[N];

cp A[N];

void DFT(cp *a, int n, int flag) {

	for(int i = 0; i < n; ++i) A[rev[i]] = a[i];

	for(int i = 0; i < n; ++i) a[i] = A[i];

	for(int m = 2; m <= n; m <<= 1) {

		cp wn(cos(2.0 * Pi / m * flag), sin(2.0 * Pi / m * flag));

		int mid = m >> 1;

		for(int i = 0; i < n; i += m) {

			cp w(1.0);

			for(int j = 0; j < mid; ++j) {

				cp u = a[i + j], t = a[i + j + mid] * w;

				a[i + j] = u + t;

				a[i + j + mid] = u - t;

				w = w * wn;

			}

		}

	}

	if (flag == -1)

		for(int i = 0; i < n; ++i)

			a[i].r /= n;

}

void init(int &n) {

	int k = 1, L = 0;

	for(; k < n; k <<= 1, ++L);

	n = k;

	for(int i = 0; i < n; ++i) {

		int t = i, ret = 0;

		for(int j = 0; j < L; ++j)

			ret <<= 1, ret |= (t & 1), t >>= 1;

		rev[i] = ret;

	}

}

void FFT(double *x, double *y, cp *a, cp *b, int len) {

	for(int i = 0; i < len; ++i) a[i].r = x[i], a[i].i = 0.0;

	for(int i = 0; i < len; ++i) b[i].r = y[i], b[i].i = 0.0;

	DFT(a, len, 1); DFT(b, len, 1);

	for(int i = 0; i < len; ++i) a[i] = a[i] * b[i];

	DFT(a, len, -1);

}

cp a[N], b[N];

int n, len;

double g[N], q[N], f[N], ans[N];

int main() {

	scanf("%d", &n); len = (n << 1) + 1;

	init(len);

	for(int i = 1; i <= n; ++i) scanf("%lf", &q[i]);

	for(int i = 1; i <= n; ++i) g[i] = 1.0 / i / i;

	for(int i = 0; i < n; ++i) f[i] = q[n - i];

	FFT(q, g, a, b, len);

	for(int i = 1; i <= n; ++i) ans[i] = a[i].r;

	FFT(f, g, a, b, len);

	for(int i = 1; i <= n; ++i) ans[i] -= a[n - i].r;

	for(int i = 1; i <= n; ++i) printf("%.3lf\n", ans[i]);

	return 0;

}

题面如下，BZOJ上没有题面喔：

Description

给出n个数qi，给出Fj的定义如下： 
【BZOJ 3527】【ZJOI 2014】力 
令Ei=Fi/qi，求Ei.

Input

第一行一个整数n。 
接下来n行每行输入一个数，第i行表示qi。

Output

n行，第i行输出Ei。 
与标准答案误差不超过1e-2即可。

Sample Input

5

4006373.885184

15375036.435759

1717456.469144

8514941.004912

1410681.345880

Sample Output

-16838672.693

3439.793

7509018.566

4595686.886

10903040.872

Hint

对于30%的数据，n≤1000。 
对于50%的数据，n≤60000。 
对于100%的数据，n≤100000，0<qi<1000000000。

Source

感谢nodgd放题

相关文章