Description

给出n个数qi,给出Fj的定义如下:
令Ei=Fi/qi,求Ei.

Input

第一行一个整数n。
接下来n行每行输入一个数,第i行表示qi。
n≤100000,0<qi<1000000000

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
首先将公式里的q[i]消去  然后直接写就可以发现前半个sigma已经是卷积的形式了 那么针对后面的sigma我们直接采取换元的形式发现如果把式子倒着来  然后再* 那个平方项就又是一个卷积形式了 做两次fft即可
$Ei=\sum_{i>j}^{}{qj \over (i-j)^2}-\sum_{i<j}^{}{qj \over (j-i)^2}$
$Ei=\sum_{j=1}^{i-1}{qj \over (i-j)^2}-\sum_{j=i+1}^{n}{qj \over (j-i)^2}$
$Ei=\sum_{j=1}^{i-1}{a[j]*b[i-j]}-\sum_{j=i+1}^{n}{a[j]*b[j-i]} $
$a[i]=qi,b[i]={1 \over i^2}$
$\sum_{j=0}^{n-1-i}{a[n-1-j]*b[j-i]}$

 

分类: fft数学

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论