[ZJOI2014]力 题解

题意：

发现Ei如果给出了Fi就很好算，所以目标其实是算Fi.
首先我们令$F_j=A_j-B_j$.
其中$A_j=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}.$

$$B_j=\sum_{i>j}\frac{q_iq_j}{(i-j)^2}.$$

考虑将第一个式子变形为

$$A_j=\sum_{i=0}^{j-1}\frac{q_iq_j}{(i-j)^2}.$$

由乘法分配律，可以将$q_j$单拎出来，得：

$$A_j=q_j\times \sum_{i=0}^{j-1}\frac{q_i}{(i-j)^2}.$$

由于$(i-j)^2=(j-i)^2$，所以考虑这样一个函数：

$$g(x)=\frac{1}{x^2}.$$

然后就会发现可以把

$$\frac{q_i}{(i-j)^2}$$

变形为

$$q_ig(j-i).$$

带回原式，得到：$A_j=q_j\times \sum_{i=0}^{j-1}q_ig(j-i).$
不难发现后面的那坨东西类似于多项式乘法，但是少了一项，可以手动将$g(0)=0$.
然后…这就是个多项式乘法的典型形式！可以用$\text{FFT}$解决！
同理也可以化简$B_j$.

$$B_j=\sum_{i=j+1}^{n-1} \frac{q_iq_j}{(i-j)^2}$$ $$B_j=q_j\sum_{i=j+1}^{n} \frac{q_i}{(i-j)^2}$$

然后突然发现…这东西和$A_j$的计算方法不大一样!咋整？
瞬间考虑->反转q序列！变成

$$\sum_{i=0}^{j-1}\frac{q'_i}{(i-j)^2}.$$

然后把这个式子搞一下，变成

$$\sum_{i=0}^{j-1}q'_ig(j-i)$$

发现这个式子本质上就是$A_j$，就能做了。