# FFT应用总结

#### bzoj3527

##### 题意

$$F_j = \sum_{i< j}{q_iq_j\over (i – j)^2}-\sum_{i>j}{q_iq_j\over (i – j)^2}$$

##### 题解

$$F_i = \sum_{j< i}{q_iq_j\over (j – i)^2}-\sum_{j>i}{q_iq_j\over (j – i)^2}$$

\begin{aligned} E_i &= {F_i \over q_i}\\ &=\sum_{j< i}{q_j\over (j – i)^2}-\sum_{j>i}{q_j\over (j – i)^2}\\ &=\sum_{j=1}^{i-1}{q_j\over (j – i)^2}-\sum_{j=i+1}^n{q_j\over (j – i)^2}\\ &设 g_i = {1\over i^2}\;\;\; f_i = q_i\\ E_i &=\sum_{j=1}^{i-1}{f_jg_{i – j}}-\sum_{j=i+1}^n{f_jg_{j – i}}\\ \end{aligned}

$$\sum_{j = i+1}^nf_jg_{j – i}$$

$$\sum_{j + i = i+1}^nf_{j + i}g_{j + i – i}$$

$$\sum_{j = 0}^{n -i}f_{j+i}g_j$$

$$\sum_{n-i-j=0}^{n-i}f_{n-i-j+i}g_{n-i-j}$$

$$\sum_{j=0}^{n-i}f_{n-j}g_{n-i-j}$$

$$\sum_{j = 0}^tf_{n-j}g_{t-j}$$

$$\sum_{j=0}^t f’_jg_{t-j}$$

。。

#### bzoj 2194

##### 题意

$$c_k=\sum_{k\leq i< n}a_ib_{i-k}$$

##### 题解

\large \begin{aligned} c_k &= \sum_{k \leq i \leq n-1}a_ib_{i-k}\\ &= \sum_{0\leq i-k \leq n-k-1} a_ib_{i-k}\\ &= \sum_{0 \leq j \leq n-k-1} a_{j+k}b_j \;\;\;\;(j=i-k)\\ & 设 \; N=n-k-1,c’_N=c_k\\ c’_N &= \sum_{0 \leq j\leq N}a_{n-1-(N-j)}b_j\\ & 设 \; a’_{N-j}=a_{n-1-(N-j)},a’_{i}=a_{n-1-i}\\ c’_N &= \sum_{0 \leq j\leq N}a’_{N-j}b_j \end{aligned}

。。

#### bzoj 3771

*顺序不同算一种

##### 题解

$${A^3(x)-3A(x)·B(x)+2C(x)\over 6}+{A^2(x)-B(x)\over 2}+A(x)$$

#### bzoj 3513

##### 题解

$$B_i = \sum A_j \times A_{i-j}$$

#### bzoj 4259

##### 题解

$$dis(A,B) = \sum_{i = 0}^{n-1}(A_i – B_i)^2 [A_i != *][B_i!=*]$$

$$dis(A,B) = \sum_{i = 0}^{n – 1}(A_i-B_i)^2A_iB_i$$

$$f_i = \sum_{i = 0}^{m – 1} (A_j – B_{i – m + 1 + j})^2A_jB_{i – m + 1 + j}$$

\begin{aligned} f_i &= \sum_{j = 0}^i(A_j – B_{i – j})^2A_jB_{i – j}\\ &=\sum_{j = 0}^i(A_j^2-2A_jB_{i – j} + B_{i – j}^2)A_jB_{i – j}\\ &=\sum_{j = 0}^iA_j^3B_{i – j}-2\sum_{j = 0}^iA_j^2B_{i – j}^2+\sum_{j = 0}^iA_jB_{i – j}^3\\ \end{aligned}

。。

（需要有优越的调参技术

### 1 COMMENT

1. Fop_zz2018-03-13 上午11:37

资瓷啊

×