BZOJ3527 - Click Here
Description
给出n个数qi，给出Fj的定义如下：
$F_j=\sum_{i>j} \frac{q_i q_j}{(i-j)^2}-\sum_{i<j} \frac{q_i q_j}{(i-j)^2}$
令Ei=Fi/qi，求Ei.
Input
第一行一个整数n。
接下来n行每行输入一个数，第i行表示qi。
n≤100000，0<qi<1000000000
Output
n行，第i行输出Ei。与标准答案误差不超过1e-2即可。
Solution
FFT裸题。但还是记录一下，毕竟有个常见的trick。
为了看起来更直观，我们定义两个函数$f(i)=q_i, \, g(i)=\begin{cases} \frac{1}{i},i>0 \\ 0,i=0 \end{cases}$
题目求$E_i=\sum_{i>j}\frac{q_j}{(i-j)^2}-\sum_{i<j} \frac{q_j}{(i-j)^2}$
该式等价于$E_i=\sum_{j=0}^{i}f(j) \times g(i-j)-\sum_{j=i}^{n}f(j) \times g(j-i)$
定义$E1_i=\sum_{j=0}^{i}f(j) \times g(i-j), \, E2_i=\sum_{j=i}^{n}f(j) \times g(j-i)$
则$E1_i$是一个卷积形式，直接FFT加速即可。
考虑$E2_i$的求解。
$E2_i=\sum_{j=i}^{n}f(j) \times g(j-i) = \sum_{j=0}^{n-i} f(j+i) \times g(j)$
定义一个新的函数$f’(i)=f(n-i)$，然后上式等价于$E2_i=\sum_{j=0}^{n-i} f’(n-j-i) \times g(j)$
这样$E2_i$也是一个卷积形式，直接FFT加速就好啦。
CODE
CODE - Click Here