Solution

首先化简 Ej\sf E_jEj​ 得到

Ej=Fjqj=∑i=1j−1qi×qj(i−j)2−∑i=j+1nqi×qj(i−j)2qj\Large E_j = \dfrac{F_j}{q_j}=\dfrac{\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}}{q_j}Ej​=qj​Fj​​=qj​∑i=1j−1​(i−j)2qi​×qj​​−∑i=j+1n​(i−j)2qi​×qj​​​

假设 f1(x)=qx,f2(x)=1x2f1(x) = q_x, f2(x)=\frac{1}{x^2}f1(x)=qx​,f2(x)=x21​。

那么原始可以化简：Ej=∑i=1j−1qi×qj(i−j)2−∑i=j+1nqi×qj(i−j)2=∑i=1j−1(f1(i)−f2(i−j))−∑i=j+1n(f1(i)−f2(j−i))\Large E_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}=\sum_{i=1}^{j-1}(f1(i)-f2(i-j))-\sum_{i=j+1}^n (f1(i)-f2(j-i))Ej​=∑i=1j−1​(i−j)2qi​×qj​​−∑i=j+1n​(i−j)2qi​×qj​​=∑i=1j−1​(f1(i)−f2(i−j))−∑i=j+1n​(f1(i)−f2(j−i))

前半部分是一个卷积的形式。

后半部分考虑定义 f1f1f1 函数的反转是 ggg。

那么容易发现有 ∑i=0n−jg(n−j−i)∗f2(i)\sum_{i=0}^{n-j} g(n-j-i)*f2(i)∑i=0n−j​g(n−j−i)∗f2(i)。也是卷积的形式。

然后随便跑一个FFT就能过了。