[ZJOI2014] 力

ID: 2387

远端评测题

3000ms

125MiB

难度: 6

上传者:

标签>

数学

2014

浙江

Special Judge

快速傅里叶变换 FFT

题目描述

给出 $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}$ 时即被认为正确。

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

【数据范围】
对于 $30\%$ 的数据， $n \leq 1000$ ；
对于 $50\%$ 的数据， $n \leq 6 \times 10^4$ ；
对于 $100\%$ 的数据， $1 \leq n \leq 10^5$ ， $0 < q_i < 10^9$ 。