基础多项式的自闭学习历程

写在前面

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

多项式

多项式的定义

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

[A(x)=sumlimits_{i=0}^{n}a_ix^i ]

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

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

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

多项式运算

加减法

加减法比较好理解.

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

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

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

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

乘法

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

卷积

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

[c_k=sumlimits_{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)=sumlimits_{i=0}^{n}sumlimits_{j=0}^{n}a_ib_jx^{i+j}=sumlimits_{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)=sumlimits_{i=0}^{n-1}y_ifrac{prodlimits_{j e i}(x-x_j)}{prodlimits_{j e 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{2pi i}{n})=cosfrac{2pi}{n}+isinfrac{2pi}{n})是一个本原单位根。下文首先考虑负数域(C)上的多项式。

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

离散傅里叶变换（DFT）

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

[b_k=sumlimits_{i=0}^{n-1}a_icdot omega_n^{ ki} ]

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

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

离散傅里叶逆变换（IDFT）

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

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

[b_k=sumlimits_{i=0}^{n-1}a_icdot omega_n^{ ki}(0leq k < n) ]

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

[a_k=frac 1nsumlimits_{i=0}^{n-1}b_icdot omega_n^{ -ki}(0leq k < n) ]

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

快速傅里叶变换（FFT）

引子—循环卷积

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

[c_k=sumlimits_{(i+j) ext{mod} n=k}a_ib_j ]

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

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

(mathcal{F}(mathbf{a*b})=mathcal{F}(mathbf a)cdotmathcal{F}(mathbf b))

其中(cdot)表示逐点乘积

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

？？

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

然后

不会没了