「笔记」基础多项式的自闭学习历程

写在前面

看洛谷网课学的
规定字母的加重字体为一个数列，如\(a\)的加重字体为\(\mathbf a\)，\(\mathbf a\)即为一个数列
博猪现在的水平，不足以继续往下学习了，所以……咕咕咕
我一定会更新哒！

多项式

多项式的定义

一个环\(R\)上的关于\(x\)的多项式可以写作

\[A(x)=\sum\limits_{i=0}^{n}a_ix^i \]

其中\(a_i\in R\)，被称为这个多项式的系数。\(x\)是一个不在环上的元素，只起一个占位的作用，并没有实际的意义，被称为这个多项式的自由元。

多项式的次数被定义为其最高非零次项的次数，记为\(\deg A(x)\)

可以认为\(FFT\)是在复数域上的操作，\(NTT\)是在有限域上的操作

多项式运算

加减法

加减法比较好理解.

设\(A(x),B(x)\)是次数不超过\(n\)的多项式。

那么加法和减法运算被定义为：

\[A(x)\pm B(x)=\sum_{i=0}^{n}(a_i\pm b_i)x^i \]

显然可以在\(O(n)\)时间内计算这两个多项式的和或差。

乘法

乘法可能不那么好理解，所以我们要先接触一个概念：卷积

卷积

设\(\mathbf{a,b}\)是两个数列，那么这两个数列的卷积\(\mathbf c\)的定义为

\[c_k=\sum\limits_{i+j=k}a_ib_j \]

\(eg.\)

假设现在我们有\(\mathbf{a,b}\)两个数列，数列中的值分别为\(a_0,a_1,a_2\)和\(b_0,b_1,b_2\)，那么这两个数列的卷积\(\mathbf c\)中的元素就是\(c_0=a_0b_0,c_1=a_0b_1+a_1b_0,c_2=a_0b_2+a_1b_1+a_2b_0\)，也就是说原数列元素的下标之和等于新的下标

多项式乘法

两个多项式的乘积被定义为：

\[A(x)B(x)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n}a_ib_jx^{i+j}=\sum\limits_{i=0}^{2n}c_kx^k \]

其中\(\mathbf c\)是\(\mathbf a\)和\(\mathbf b\)的卷积。朴素地按定义计算多项式乘法的时间复杂度是\(O(n^2)\)的

\(ps:\)两个多项式的乘法不一定要同次

多项式的点值表示

给定一个不超过\(n\)次的多项式\(A(x)\)以及\(n+1\)个不同的点\(x_0,x_1,x_2,…,x_n\)，令\(y_i=A(x_i)\)。

则这\(n+1\)组\((x_i,y_i)\)唯一的确定了这个多项式\(A(x)\)。这些点\((x_i,y_i)\)称作这个多项式的点值表示。（其实也可以用向量表示）

假设给出了\(n+1\)个点\((x_0,y_0),…(x_n,y_n)\)（\(x_i\)互不相同），要求找出一个过所有点的多项式函数\(A(x)\)，则可以用高斯消元法求出，但是高斯消元时间复杂度比较高而且有精度误差，这个时候我们就可以考虑用拉格朗日插值了

拉格朗日插值公式

\[A(x)=\sum\limits_{i=0}^{n-1}y_i\frac{\prod\limits_{j\ne i}(x-x_j)}{\prod\limits_{j\ne i}(x_i-x_j)} \]

利用拉格朗日插值公式可以在给定\(n\)个点值表示法的情况下\(O(n^2)\)时间内计算出原二项式在某个位置的值

如果给出\(A(x)\)和\(B(x)\)分别在\(x_0,x_1,…,x_n\)下的点值，则可以在\(O(n)\)时间内得到 \(A(x)\pm B(x)\)或\(A(x)B(x)\)在同一组位置处的点值。

前置知识

复数

咕咕咕（我还不知道怎么简洁地叙述

单位根

满足\(x^n-1=0\)的\(x\)被称作\(n\)次单位根。

设\(\omega\)是\(n\)次单位根。如果恰好\(\omega^0,\omega^1,…\omega^{n-1}\)生成了所有的\(n\)次单位根（即两两不同），则称\(\omega\)为本原单位根。这等价于\(n\)是最小的使得\(\omega^n-1=0\)的正整数。我们\(\omega_n\)来表示一个\(n\)次本原单位根。

在复数域\(\C\)上，\(\omega_n=\exp(\frac{2\pi i}{n})=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}\)是一个本原单位根。下文首先考虑负数域\(\C\)上的多项式。

在有限域（即模素数的情况）中，本原单位根与数论中的原根有关。

离散傅里叶变换（DFT）

设\(\mathbf a\)是长度为\(n\)的数列，对\(0\leq k < n\)，令

\[b_k=\sum\limits_{i=0}^{n-1}a_i\cdot \omega_n^{\ ki} \]

则称\(\mathbf b\)为\(\mathbf a\)的离散傅里叶变换（\(\text{DFT}\)），记作\(\mathbf b=\mathcal{F}(\mathbf a)\)，\(\mathcal{F}\)就表示离散傅里叶变换。

容易看出，令\(A(x)=\sum a_ix^i\)，则\(b_k\)就是\(A(x)\)在\(\omega_n^{\ k}\)处的点值。因此计算\(\mathbf a\)的\(\text{DFT}\)与计算\(A(x)\)在\(\omega_n^{\ 0},\omega_n^{\ 1},…,\omega_{n}^{\ n - 1}\)处的点值表示是等价的。

离散傅里叶逆变换（IDFT）

~~\({\text{IDFT}}\)是啥？能吃吗？~~

对于长度\(n\)为的序列\(\mathbf{a,b}\)，回忆\(\text{DFT}\)的定义：

\[b_k=\sum\limits_{i=0}^{n-1}a_i\cdot \omega_n^{\ ki}(0\leq k < n) \]

则\(\text{DFT}\)的逆变换\(\text{IDFT}\)如下：

\[a_k=\frac 1n\sum\limits_{i=0}^{n-1}b_i\cdot \omega_n^{\ -ki}(0\leq k < n) \]

\(\text{IDFT}\)是\(\text{DFT}\)的逆变换，也就意味着已知多项式在单位根处的点值，\(\text{IDFT}\)能够求出多项式的各项系数。在这种意义上，这个过程也可以看作插值。

快速傅里叶变换（FFT）

引子—循环卷积

对于两个长度为\(n\)的序列\(\mathbf{a,b}\)，定义

\[c_k=\sum\limits_{(i+j)\text{mod}\ n=k}a_ib_j \]

则称\(\mathbf c\)为\(\mathbf a\)与\(\mathbf b\)的循环卷积，记为\(\mathbf{c=a*b}\)。

关于循环卷积与\(\text{DFT}\)，我们有如下定理：

\(\mathcal{F}(\mathbf{a*b})=\mathcal{F}(\mathbf a)\cdot\mathcal{F}(\mathbf b)\)

其中\(\cdot\)表示逐点乘积

白话就是\(\mathbf a\)和\(\mathbf b\)的循环卷积的离散傅里叶变换等于\(\mathbf a\)的离散傅里叶变换逐点乘上\(\mathbf b\)的离散傅里叶变换（显然很啰嗦，还是看式子⑧）

？？

上面的离散傅里叶变换（\(\text{DFT}\)）计算卷积的复杂度是\(O(n^2)\)的，快速傅里叶变换是快速计算 \(\text{DFT}\)的方法，可以优化到\(O(n \log n)\)

然后

不会没了