传送门
看来对 FFT 的理解仍只是在表层模板而已，对问题还是不会转化
思路
我们先回顾卷积的形式：
\[W_k=\sum_{i=0}^kF_i\times G_{k-i}
\]
这些表示的都是系数
回到这道题，题目其实让我们求得应该是 \(E_i=\sum_{j=1}^{i-1}\frac{q[j]}{(i-j)^2}-\sum_{j=i+1}^{n}\frac{q[j]}{(j-i)^2}\)
因为这是板子题， 我们应该要将式子转化成卷积的形式
我们令 \(F[k]=q[k], G[k]=\frac{1}{k^2}\)，因此有
\[E_i=\sum_{j=1}^{i-1}F[j]G[i-j]-\sum_{j=i+1}^{n}F[j]G[j-i]
\]
我们考虑让 \(F[0]=G[0]=0\)，让形式更靠近卷积的形式:
\[E_i=\sum_{j=0}^{i}F[j]G[i-j]-\sum_{j=i}^{n}F[j]G[j-i]
\]
右式的左半部分成功化成卷积形式了，但右边还是差点
我们考虑令 \(j=0\)：
\[E_i=\sum_{j=0}^{i}F[j]G[i-j]-\sum_{j=0}^{n-i}F[j+i]G[j]
\]
我们再考虑令 \(F'[k]=F[n-k]\)
\[E_i=\sum_{j=0}^{i}F[j]G[i-j]-\sum_{j=0}^{n-i}F'[n-i-j]G[j]
\]
这时我们就成功转化了，为了让式子更好看，我们令 \(r=n-i\)
\[E_i=\sum_{j=0}^{i}F[j]G[i-j]-\sum_{j=0}^{r}F'[r-j]G[j]
\]
开卷！
令函数 \(A(x),B(x),C(x)\) 的系数表示分别为 \(\{F[k]|0\le k\le n\},\{F'[k]|0\le k\le n\},\{G[k]|0\le k\le n\}\)
求出 \(X(x)=A(x)*C(x)\), \(Y(x)=B(x)*C(x)\)
最后的答案就为 \(E_i=X_i-Y_{n-i}\)
代码
#include
#include
#include
#include
#include
#include
#include
#include