省选-数学-FFT · Zhl2010 第二博客

一个 $n$ 次多项式可以被 $(x_i,y_i)$ 这种的 $n+1$ 个点表示。

比较显然的。

FFT 就是利用这种性质，来求解答案。我们需要一个快速将系数表示法转换成点表示法的东西。

这里面还需要一些复数的性质，先看看复数相乘：

\begin{align*} (a+bi)*(c+di) &= ac+adi+bci+bdi^2\\ &= ac+adi+bci-bd\\ &= (ac-bd)+(bc+ad)i \end{align*}

为了方便说明， $n$ 先设为 $2$ 的整次幂。在复平面上，以单位圆的 $n$ 等分点为终点，做 $n$ 个向量， $\omega_n^2,\omega_n^3,\ldots,\omega_n^n$ 。

性质：

\omega^{k}_n=\omega^{2k}_{2n}

\omega^n_n=1\\ \omega^{\frac n 2}_n=-1

z^2 = (a+bi)^2 = a^2 + 2abi + (bi)^2 = a^2 - b^2 + 2abi\\ z^2 = (\cos^2\theta - \sin^2\theta,\; 2\cos\theta\sin\theta) = (\cos 2\theta,\; \sin 2\theta)

$A(x)=a_0+a_1*x+a_2*{x^2}+a_3*{x^3}+a_4*{x^4}+a_5*{x^5}+ \dots+a_{n-2}*x^{n-2}+a_{n-1}*x^{n-1}$

按照奇偶性拆分：

$A_1(x)=a_0+a_2*{x}+a_4*{x^2}+\dots+a_{n-2}*x^{\frac{n}{2}-1}$

$A_2(x)=a_1*x+a_3*{x}+a_5*{x^2}+ \dots+a_{n-1}*x^{\frac{n}{2}-1}$

所以：

$A(x)=A_1(x^2)+xA_2(x^2)$

$A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})$

\begin{align*} A(\omega_n^{k+\frac{n}{2}})\\ &=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}(\omega_n^{2k+n})\\ &=A_1(\omega_n^{2k}\times\omega_n^n)-\omega_n^kA_2(\omega_n^{2k}\times\omega_n^n)\\ &=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k}) \end{align*}

对比这两个式子：

$A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})$

A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k})

所以我们枚举第一个式子的时候可以 $O(1)$ 计算第二个式子的值。

我们还需要一个逆变换。

nA(x) = c_0 + c_1 x + c_2 x^2 + \dots + c_{n-1} x^{n-1}\\ a_k=\frac{c_k}{n}

c_k = \sum_{i=0}^{n-1} y_i \, (\omega_n^{-k})^i

$B(x)=y_0+y_1x+y_2x^2+\dots+y_{n-1}x^{n-1}$

$c_k=B(\omega_n^{-k})$

怎么证明？

将 $y_i = \sum_{j=0}^{n-1} a_j \omega_n^{ij}$ 代入 $c_k$ ：

c_k = \sum_{i=0}^{n-1} \left( \sum_{j=0}^{n-1} a_j \omega_n^{ij} \right) \omega_n^{-ik} = \sum_{j=0}^{n-1} a_j \sum_{i=0}^{n-1} \omega_n^{i(j-k)}

内层和式 $S = \sum_{i=0}^{n-1} (\omega_n^{j-k})^i$ 是等比数列求和：

若 $j = k$ ，则 $\omega_n^{0}=1$ ， $S = n$
若 $j \neq k$ ，则 $\omega_n^{j-k} \neq 1$ ，且 $(\omega_n^{j-k})^n = 1$ ，由等比数列求和公式得：

S = \frac{1 - (\omega_n^{j-k})^n}{1 - \omega_n^{j-k}} = \frac{1-1}{1-\omega_n^{j-k}} = 0

因此 $c_k = a_k \cdot n$ ，即 $a_k = c_k / n$ 。证毕。

所以逆变换公式就是：

a_k = \frac{1}{n} \sum_{i=0}^{n-1} y_i \, \omega_n^{-ik}

也就是逆变换只需要把正变换的 $\omega$ 取一个相反数就行了。

A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k})

小优化：

我们可以把 $b(x)$ 放到 $a(x)$ 的虚部上去，求出 $a(x)^2$ ，然后把 $a(x)$ 的虚部取出来除 $2$ 就是答案了。

\large (a+bi)^2=(a^2-b^2)+(2abi)

这样就只需要 $3$ 次 FFT 了。

我们发现如果直接用 FFT 中 double 精度不够， $10^{23}$ 完全不行。

A(x) = A_0(x) \cdot M + A_1(x), \quad B(x) = B_0(x) \cdot M + B_1(x)

A\cdot B = (A_0B_0) M^2 + (A_0B_1 + A_1B_0) M + A_1B_1

我们只需要用 $4$ 次 FFT 递归下去（显然递推也行），求出这四个值加起来。

P_k = (A_0)_k (B_0)_k + i \cdot (A_1)_k (B_0)_k\\ Q_k = (A_0)_k (B_1)_k + i \cdot (A_1)_k (B_1)_k

这样的话只有不到 $10^{14}$ 次。