[ZJOI2014]力

题目描述

给出n个数qi，给出Fj的定义如下：

$Fj = \sum{ij}\frac{q_i q_j}{(i-j)^2 }$

令$Ei=Fi/qi$，求Ei.

输入格式：

第一行一个整数n。

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

输出格式：

n行，第i行输出Ei。

与标准答案误差不超过1e-2即可。

输入样例#1：

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

输出样例#1：

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

对于30%的数据，n≤1000。

对于50%的数据，n≤60000。

对于100%的数据，$n≤100000，0<qi<1000000000$。

一上午就搞了一道大水题。。。。（昨晚没睡好的后果）

具有创造力的（套路的）构造多项式：

$F(x)=\sum\limits_{i=1}^{n}q_ix^i$

$G(x) = \sum\limits_{i=1}^{n}\frac{1}{i^2}x^i$

系数使用多项式的小写字母表示

答案可以由这两个多项式卷积求得！

$H(x) = (\sum\limits{i=1}^{n}(\sum\limits{j=1}^{i-1}\frac{qj}{(i-j)^2 }-\sum\limits{j=i+1}^{n}\frac{q_j}{(i-j)^2})x^i$

$H(x) = \sum\limits{i=1}^{n}\sum\limits{j=1}^{i-1}qjg{i-j}x^i - \sum\limits{i=1}^{n}\sum\limits{j=i+1}^{n}qjg{j-i}x^i$

发现这其实也是$FFT$的一种卷积形式，因此直接多项式相乘。做完前面那个$FFT$，后面的发现下标相加等于$j$，不是标准的$FFT$卷积，把$f$的系数反转即可和左边一样（听说是常用技巧？）。

话说今天下午的时间基本上都给省选模拟赛了。

T1根号打表1e5还是只有50弃了（多打几十万大概70？），T2样例分，T3暴力分。

。。。感觉学了等于没学嘛。