P3338-[ZJOI2014]力
题目:
题目描述:
给出 $n$ 个数 $q_1,q_2, \dots q_n$，定义
$$F_j~=\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2}$$
$$E_i~=~\frac{F_i}{q_i}$$
对 $1 \leq i \leq n$，求 $E_i$ 的值。
输入格式:
第一行输入一个整数 $n$。
以下 $n$ 行，每行有一个实数。第 $i+1$ 行的数代表 $q_i$。
输出格式:
输出 $n$ 行每行一个实数，第 $i$ 行的数字代表 $E_i$。
当你的输出与标准答案相差不超过 $10^{-2}$ 时即被认为正确。
样例:
样例输入 1:
1
2
3
4
5
6
| 5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
|
样例输出 1:
1
2
3
4
5
| -16838672.693
3439.793
7509018.566
4595686.886
10903040.872
|
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include "ybwhead/ios.h"
using namespace std;
int lim = 1, l;
const int maxn = 6e5 + 10;
// #define double long double
struct com
{
long double x, y;
com() : x(0), y(0) {}
com(long double a, long double b) : x(a), y(b) {}
com operator+(com a)
{
return com(x + a.x, y + a.y);
}
com operator-(com a)
{
return com(x - a.x, y - a.y);
}
com operator*(com a)
{
return com(x * a.x - y * a.y, x * a.y + y * a.x);
}
};
com a[maxn], b[maxn];
int r[maxn];
const long double pi = acos(-1);
void fft(com a[], int x)
{
for (int i = 0; i < lim; i++)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int o = 2, k = 1; o <= lim; o <<= 1, k <<= 1)
{
com wn(cos(pi / k), x * sin(pi / k));
for (int i = 0; i < lim; i += o)
{
com w(1, 0);
for (int j = 0; j < k; j++, w = w * wn)
{
com x = a[i + j], y = w * a[i + j + k];
a[i + j] = x + y;
a[i + j + k] = x - y;
}
}
}
return;
}
int n;
int main()
{
yin >> n;
for (int i = 0; i < n; i++)
{
yin >> b[i].x;
}
for (int i = -n + 1; i <= n - 1; i++)
{
if (i < 0)
a[i + n - 1].x = -(long double)1.0 / i / i;
else if (i == 0)
a[i + n - 1].x = 0;
else
a[i + n - 1].x = (long double)1.0 / i / i;
}
while (lim < (n * 3))
lim <<= 1, ++l;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
fft(a, 1);
fft(b, 1);
for (int i = 0; i < lim; i++)
a[i] = a[i] * b[i];
fft(a, -1);
for (int i = 0; i < n; i++)
{
yout << (a[i + n - 1].x) / lim << endl;
}
}
|