标签：多项式 FFT 表示法 2n omega 我们

多项式，FFT

Polynomial Convolution

若 $A(x)$ 与 $ B(x)$ 分别为两个多项式，则两个多项式的卷积为：
$$
A(x)\cdot B(x)=\sum_{i=0}^n\sum_{j=0}ia_jb_{i-j}
$$
其中，$ A(x) $ 与 $B(x)$ 都是 $n-1$ 次的多项式

Dot Method

通常我们在存储多项式的时候会有一个很自然的想法：将多项式升幂/降幂排列，然后存储各次项系数

这种方法我们称其为系数表示法

然而系数表示法在计算多项式乘法时时间复杂度达到了难以优化的$O(n^2)$，是不可接受的

所以我们必须找到另一种表示多项式的更好计算的方法，也就是点值表示法，它依赖于这条定理

定理 $1$：

任何一个 $n$ 次多项式都可以由平面上的 $n+1$ 个点唯一确定

所以我们只要计算出 $n+1$ 个 $x$ 对应的 $A(x)$ 就可以存下这条多项式。

从而，如果我们要求两个 $n$ 次多项式 $A(x)$ 和 $B(x)$ 的乘积 $A(x)\cdot B(x)$，只要求出 $2n+1$ 个点的值，然后对他们做乘积即可。
$$
A(x)=(x_0,y_0),(x_1,y_1)....(x_{2n},y_{2n})\B(x)=(x_0,y^{′_0),(x_1,y}′1)....(x{2n},y^′{2n})
$$
则
$$
A(x)B(x)=(x_0,y_0y^{′_0),(x_1,y_1y}′1)⋯(x{2n},y{2n}y^′_{2n})
$$
这个算法时间复杂度为 $O(n)$ ，已经相当优秀，现在我们要考虑的问题就是：

1.如何将系数表示法转换为点值表示法？

2.如何从点值表示法转换为系数表示法？

Q1实际上就是$DFT$的过程，

而Q2实际上就是$IDFT(Inverse Discrete Fourier Transform)$的过程

FFT

$FFT$，即$Fast \ Fourier \ Transform$，离散傅里叶变换。用于优化取点算值的过程

直接算值的时间复杂度仍然达到了$O(n^2)$，这是我们所不希望的

所以我们就需要利用 $FFT$ 来优化算值的过程

首先考虑一些简单的多项式，例如
$$
f(x) \ = \ x^2
$$
在计算这个多项式的值时，我们可以取一个$x>0$的点，然后利用函数的奇偶性得到$x<0$时的情况

再例如：
$$
f(x) \ = \ x^3
$$
同样的，我们也可以只取四个点，两个$x>0$，然后再对称出另外两个点的值

啊哈！现在让我们来讨论这个方法在一般的多项式上是否还适用？

让我们考虑：
$$
P(x) \ = \ 3x^5+2x4+x^3+7x2+5x+1
$$
这个一般得多的例子

看起来似乎没有办法利用上面的规律了，但如果我们给他分个组呢？
$$
P(x) \ = \ (2x^4 + 7x^2 + 1)+x(3x^4+x2+5)
$$
我们把它分成了两个组，又在奇函数那一组里提了一个 $x$ ，现在这就是两个偶函数了

让我们分别把他们记为 $P_e(x)$ 和 $P_o(x)$ ，现在这就是两个偶函数了，而偶函数每个点和它的相反数的值都是相同的，所以不妨进一步把他们记为 $P_e(x^2)$ 和 $P_o(x^2)$ ，

——所以我们现在有
$$
P(x) \ = \ P_e(x^2)+xP_o(x2)
$$
也就是说，我们对于每一个 $x_i$ 的值，现在有
$$
P(x_i) \ = \ P_e(x_i^{2)+x_iP_o(x_i}2)\
P(-x_i) \ = \ P_e(x_i^{2)-x_iP_o(x_i}2)
$$
那么我们不难发现：计算$P_e(x^2)$ 和 $P_o(x^2)$ 的过程，恰是又一个求和的过程！

而通过把原式分奇偶的方法，我们把式子降到了$\lfloor \dfrac{x}{2} \rfloor - 1$阶

接下来我们只需要求一组点，使得它们代表的值平方满足等式即可

而且由于平方，我们求点只用求 $\lfloor \dfrac{x}{2} \rfloor - 1$ 个，剩下的都可以通过对称得到

接下来让我们递归地求 $P_e(x^2)$ 和 $P_o(x^2)$ ，时间复杂度一下就降低到了 $O(n\log n)$

等等，有一个问题：

我们在递归的时候，由于取相反数来加速计算，所以出现了平方为负数的情况！这个问题怎么解决？
$$
P[\pm x_1,\pm x_2,\cdots,\pm x_{\lfloor \frac{x}{2} \rfloor - 1}]是正负数对\
P[x_1^2,x_22,\cdots,x_{\lfloor \frac{x}{2} \rfloor - 1}^2]不是正负数对
$$

实数域不够用了，延拓到复数域！

利用单位根计算FFT

由于我们要利用复数计算，而且原式的值我们可以任取，那么为了避免加大运算的复杂程度，我们令

$x_i$ 为 $\omega^n=1$ 的解。

由于
$$
e^{i\theta} = cos \theta +i \ sin \theta
$$
令 $\theta = 2\pi$
$$
e^{2\pi i} = 1 = \omega^n\
\omega = e^{\frac{2\pi i}{n}}
$$
这个时候单位根称为主次单位根
$$
w_n=e^{\frac{2\pi i}{n}}
$$

(“也就是”这里要改成$-x_2^2$！！！！)

从最底层看起，这代表了取点的起点，由于我们总是取成对的点，所以最底层正负总是成对出现。

然后向上扩展，得到第二层的 $x_2^2$ 与 $x_1^2$ 两个点。由于成对出现，所以 $x_2^2 = -x_1^2$。从而最上层的点是 $x_1^4$。

现在我们令 $x_1=1$ ， 假设 $n$ 为 $2$ 的整数次方（如果不是就补零补到是）。

容易推到的是最高次的一层等于 $ 1 $ ,然后就是求 $\sqrt[n]1$ （代表了最底层的各个数）

也就是——求 $\omega_n$的所有值！

在计算 $FFT$ 的时候，我们跟循上面的思路，递归执行以上步骤
$$
1.判定边界条件： n=1时返回P(1)——这个时候多项式只有0次项\2.把式子拆成奇偶两部分。分别调用，并记偶数部分为 y_e ，奇数部分为y_o\
3.将两个式子合并
$$
从上面的推导中我们已经知道$x_j=\omega^j $，从树上也可以知道$y_e[j]=P_e(\omega^{{2j})，y_o[j]=P_o(\omega}{2j})$

而且由复数部分有$\omega^{{j+n/2}=-\omega}j$

所以
$$
P(\omega^{j)=y_e[j]+\omega}j y_o[j]\
P(\omega^{{j+n/2})=y_e[j]-\omega}j y_0[j]\
j\in \left{0,1,\dots(n/2-1)\right}
$$

标签：多项式,FFT,表示法,2n,omega,我们
From： https://www.cnblogs.com/lostintianyi/p/16789583.html