多项式 学习笔记

# 前言 带$*$号的只是一些与$\text{FFT}$没多大关系的东西，可以不读. 但是如果$*$章节有一个小节为**通俗的解释**，那么建议读懂**通俗的解释**部分 # 多项式的定义和性质 ## 环($*$)和域 定义了加减乘除，且关于这些运算封闭的集合成为域。域是特殊的环。 定义了加法和乘法，且关于这些运算封闭的集合成为环。 这里的加法和乘法**必须有分配律成立**。 有理数集$Q$，实数集$R$和复数集$C$都是域。 整数集$Z$是一个环，但不是一个域，因为$Z$关于除法不封闭。 > 设$p$是一个质数，那么模$p$意义下的集合${0,1,\dots,p-1}$是一个域，记为$F_p$ ## 多项式 设$R$是一个环，$a_0,a_1,\dots,a_n$为$R$中的元素且$a_n\neq 0$，$x^0$始终表示1，则 $$f(x)=\sum_{k=0}^na_kx^k$$ 称为R上次数为n的多项式。 此后涉及的所有多项式均认为是某个**域**上的多项式。 ## 卷积 对于数组$a,b,c$，令 $$c_k=\sum_{i+j=k}a_ib_j=\sum_{i=0}^ka_ib_{k-i}=\sum_{j=0}^ka_{k-j}b_j$$ 则称$c$为$a$和$b$的卷积。 ## 多项式乘法 设 $$f(x)=\sum_{k=0}^na_kx^k,g(x)=\sum_{k=0}^mb_kx^k$$ 由分配律： $$f(x)g(x)=\sum_{k=0}^{n+m}c_kx^k$$ 其中$c$为$a$和$b$的卷积 按照定义直接计算，时间复杂度为$\Theta(nm)$。 ## 多项式的点值表示($*$) 设 $f(x)=\sum_{k=0}^na_kx^k$为次数不大于$n$的多项式，对于$n+1$个点$x_0,x_1,\dots,x_n$，有 $$\begin{pmatrix}f(x_0)\\f(x_1)\\f(x_2)\\\vdots\\f(x_n)\end{pmatrix}=\left(\begin{array}{ccc}1& x_0 & x_0^2&\dots&x_0^n \\1& x_1 & x_1^2&\dots&x_1^n \\1& x_2 & x_2^2&\dots&x_2^n \\\vdots&\vdots&\vdots&\ddots&\vdots\\1& x_n & x_n^2&\dots&x_n^n \\\end{array}\right)\left(\begin{array}{ccc}a_0\\a_1\\a_2\\\vdots\\a_3\\\end{array}\right)$$ 若$x_0,x_1,\dots,x_n$不相同，则等式右边的矩阵可逆，即：. $$\left(\begin{array}{ccc}a_0\\a_1\\a_2\\\vdots\\a_3\\\end{array}\right)=\left(\begin{array}{ccc}1& x_0 & x_0^2&\dots&x_0^n \\1& x_1 & x_1^2&\dots&x_1^n \\1& x_2 & x_2^2&\dots&x_2^n \\\vdots&\vdots&\vdots&\ddots&\vdots\\1& x_n & x_n^2&\dots&x_n^n \\\end{array}\right)^{-1}\begin{pmatrix}f(x_0)\\f(x_1)\\f(x_2)\\\vdots\\f(x_n)\end{pmatrix}$$ 即$n+1$个点值对$(x_k,f(x_k))$可以唯一确定$f(x)$。 设f(x),g(x)为次数分别为$n,m$的多项式，有$n+m+1$个互不相同的点$x_0,x_1,\dots,x_{n+m}$。 **若已知所有的$f(x_k)$和$g(x_k)$，则只需$\Theta(n+m)$的时间就可以计算$f(x_k)g(x_k)$，从而唯一确定$f(x)g(x)$。** 对于$f(x)+g(x)$也是类似的。 ### 通俗的解释： > $n+1$个点值对$(x_k,f(x_k))$可以唯一确定$f(x)$ 即$n+1$个点确定一个$n$次函数。然后现在有两个次数为k的函数，已经知道他们在${x_0,x_1,\dots,x_n}$的值，那么我们无需把这两个函数的系数计算出来再$\Theta(nm)$地计算，只需要将这些取值一一相乘，然后算出相乘后的函数的系数即可。 ## 多项式的根 设$F,K$是域且$F\subseteq K$,$f(x)$是$F$上的多项式，$\alpha$是$K$中的元素。若$f(\alpha)=0$，则称$\alpha$为$f(x)$的一个根。 请注意$f(x)$的根不一定在$F$中，如$f(x)=x^2-2$是$Q$上的多项式，$\sqrt{2}$是$f(x)$的一个根，但是$\sqrt{2}$不在$Q$中。 ## 单位根 多项式$x^n-1$的根称为n次单位根。 在$C$中，多项式$x^n-1$的根有$n$个。 定义$w_n=e^{\frac{2\pi i}{n}}$， 由欧拉公式 $e^{ix}=\cos x+i\sin x$。容易验证$w_n^n$ **那么多项式$x^n-1$的根为：$1,\omega_n,\omega_n^2,\dots,\omega_n^{n-1}$，且互不相同。** ### **通俗的解释** > 将复数理解为一个数对，显然这个数对需要一个坐标系来表示。其中$(x,y)$表示复数$z=x+yi$，i为$\sqrt{-1}$。 > **复数相乘，模长相乘，幅角相加。** 模长指的是复数$(x,y)$到$(0,0)$的线段的长度，幅角指的是这条线段与x轴正半轴形成的角，这个角朝上。 >单位根指的是对于一个次数$n$，找一个复数$(x,y)$，使得该复数的n次方$=1$，显然$(1,0)$是所有n的单位根。 > 画一个以$(0,0)$为圆心，以$1$为半径的圆，那么单位根就是把这个圆平均划分成$n$段后所有的分割点，假设单位根的幅角为$\theta $，那么有$n\theta \equiv0(mod\space360)$，反复考虑“**模长相乘，幅角相加**”就可以轻易得出这个结论。 > 也就是说，画出单位圆后，把单位圆平均分割成$n$份的分割点就是$n$次单位根 >多项式$x^n-1$的根全部在离$(0,0)$距离为$1$的圆上。 > 至此，您应该明白**那么多项式$x^n-1$的根为：$1,\omega_n,\omega_n^2,\dots,\omega_n^{n-1}$，且互不相同。** 这句话了 # $\text{FFT}$ ## $\text{DFT}$ 设$a$为大小为n的数组，$f(x)=\sum_{k=0}^{n-1}a_kx^k$，定义 $$\operatorname{DFT}(\alpha)=(f(1),f(\omega_n),f(\omega_n^2),\dots,f(\omega_n^{n-1}))$$ 成为$\alpha$的离散傅里叶变换（点值表示），即$\operatorname {DFT}$。 就是将系数表示法转化为点值表达法 ## $\text{IDFT}$ $\text{DFT}$的反向操作，将点值表示转为系数表示 $\text{DFT}$把多项式转为点值表达法，再用$\text{IDFT}$转回来，就是$\text{FFT}$了 ## $\text{FFT}$ ### 闲聊 通常的$\text{FFT}$选择**单位根**或**原根**作为点值表示的点。因为他们有一些美妙的性质。可以用来优化$\text{DFT}$和$\text{IDFT}$。 ### 正文 考虑我们直接随便取几个点作为点值表示的点。这样计算会是$\Theta(nm)$的。 现在我们使用单位根。 设多项式$\text{A(x)}$的系数为$(a_0,a_1,a_2,\dots,a_{n-1})$ 即 $$A(x)=\sum _{i=0}^{n-1}a_ix^i=a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1}$$ 按下标$i$的奇偶性分类（这里我假装$n-2$是偶数，如果是奇数，与$n-1$交换即可） $$A(x)=(a_0+a_2x^2+\dots+a_{n-2}x^{n-2})+(a_1x+a_3x^3+\dots+a_{n-1}x^{n-1})$$ 按照奇数和偶数，分成两个多项式 $$A_1(x)=a_0+a_2x+a_4x^2+a_6x^3+\dots+a_{n-2}x^{\frac{n}{2}-1}$$ $$A_2(x)=a_1+a_3x+a_5x^2+a_7x^3+\dots+a_{n-1}x^{\frac{n}{2}-1}$$ 有$A(x)=A_1(x^2)+xA_2(x^2)$ 将刚刚的单位根$\omega_{n}^k(k<\frac{n}{2})$代入，得到 $A(\omega_{n}^k)=A_1(\omega^{2k}_{n})+\omega_n^kA_2(\omega^{2k}_{n})=A_1(\omega^k_{\frac{n}{2}})+w^k_nA_2(\omega^k_{\frac{n}{2}})$ 同理带入$\omega_{n}^{k+\frac{n}{2}}(k<\frac{n}{2})$，得到$A_1(\omega^k_{\frac{n}{2}})-w^k_nA_2(\omega^k_{\frac{n}{2}})$ 也就是说如果我们得知$A_1(\omega^k_{\frac{n}{2}})$和$w^k_nA_2(\omega^k_{\frac{n}{2}})$的值，那就能同时算出两个式子的值。 那么我们枚举$k(k<\frac{n}{2})$，算出两个式子的值。这个时候我们变成了只需要计算$A_1$的系数 不断分成两半分治，直到剩下常数项直接返回。这样复杂度为$\Theta(nlogn)$