多项式
一些定义
-
若 \(a_n\not= 0\)?，则称 \(n\)? 是 \(f\)?? 的次数，记作 \(\operatorname{deg}(f)=n\)?，并称 \(a_n\)? 为 \(f\)? 的首项系数。
-
若 \(a_n=1\)，则称 \(f\)? 为首一多项式。?
-
规定 \(\operatorname{deg}(0)=-\infty\)?
-
\(\operatorname{deg}(f(x)+g(x))\leq \max(\operatorname{deg}(f(x)),\operatorname{deg}(g(x)))\)
-
\(\operatorname{deg}(f(x)g(x))=\operatorname{deg}(f(x))+\operatorname{deg}(g(x))\)
-
\([x^n]f(x)\) 表示 \(f(x)\) 中 \(x^n\)? 项的系数。
-
多项式 \(\not=\) 多项式函数。
多项式的表示
- 系数表示法
对于多项式：
称 \((a_0,a_1,a_2,\cdots,a_n)\)? 为多项式的系数表示。
- 点值表示法
在 \(f(x)\)? 定义域内选择至少 \(n+1\) 个数 \(x_0,x_1,x_2,\cdots,x_n\) 代入多项式得到 \(n+1\) 个值。
称 \(((x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n)))\)??? 为多项式的点值表示。
单位根
- 定义
在代数中，若 \(z^n=1|z\in \C\)，则称 \(z\) 为 \(n\)? 次单位根。
根据复数的相关知识，不难看出 \(n\) 次单位根就是在复平面单位圆上，把单位圆 \(n\)? 等分得到的顶点，这样的顶点一共有 \(n\) 个，且将其顺序相连可以构成一个正 \(n\) 边形。
欧拉公式：\(e^{ix}=\cos x+i\sin x\)
根据欧拉公式，容易得到 \(n\) 个单位根为 \(e^{\dfrac{2\pi ki}{n}}(k\in[0,n-1])\)
为了方便，我们设 \(\omega_n=e^{\dfrac{2\pi i}{n}}\)，则单位根可以表示为 \(\omega_n^i (i\in[0,n-1])\)?
- 性质和推广公式
\(\omega_n^k=\cos k \dfrac{2\pi}{n}+i\sin k\dfrac{2\pi}{n}\)
由上述公式展开得到。
\(\omega_{2n}^{2k}=\omega_n^k\)
证明：
\(\omega_n^\dfrac{n}{2}=-1\)?
证明：
\(\omega_n^0=\omega_n^n=1\)
证明：
多项式乘法
- 定义
- 朴素做法
对于系数表示法而言，我们可以直接通过上述方法计算，时间复杂度：\(O(n^2)\)??
对于点值表示法而言，乘法就是把对应点点值相乘，时间复杂度 \(O(n)\)
- 离散傅里叶变换 (DFT)
把 \(n\)? 个 \(n\)? 次单位根代入多项式得到一个特殊的点值表示的过程称为离散傅里叶变换 (DFT)。
- 离散傅里叶逆变换 (IDFT)
将 DFT 得到的点值表示转化为系数表示的过程称为离散傅里叶逆变换 (IDFT)。
- 快速傅里叶变换 (FFT)
虽然 DFT 可以把多项式系数表示转化为点值表示，但时间复杂度依然是 \(O(n^2)\)???，考虑通过单位根的性质进行优化。
首先设多项式 (注意这里为 \(n-1\)? 次多项式，且 \(n\)? 为 \(2\)? 的次幂)：
按照每项次数的奇偶进行分类，再提出奇数边的 \(x\)?，不难得到：
这两边看起来非常相似，我们再设：
显然：
设 \(k<\dfrac{n}{2}\)，把 \(x=\omega_n^k\) 代入上式得到：
再代入 \(x=\omega_n^{k+\dfrac{n}{2}}\)? 得到：
我们发现这两个多项式展开后只有符号不同，也就是说如果我们知道 \(f_1(\omega_\dfrac{n}{2}^k)\)? 和 \(f_2(\omega_\dfrac{n}{2}^k)\)??，就可以计算出 \(f(\omega_n^k)\) 和 \(f(\omega_n^{k+\dfrac{n}{2}})\)
于是我们就可以递归分治 FFT 了。
时间复杂度：\(O(n\log n)\)?
- 蝴蝶变换
为了降低递归带来的常数，我们尝试用迭代替换递归。
不难发现最后的序列是将原序列数字二进制水平翻转之后的结果。
所以我们只需一开始就翻转，后面用迭代模拟递归过程即可。
for(int i=0;i<n;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
其中 \(\rm bit\)?? 就是二进制位数。
- 快速傅里叶逆变换 (IFFT)
结论：把原多项式的 DFT 结果作为新多项式的系数，把单位根的倒数 \(x=\{\omega_n^0,\omega_n^{-1},\cdots,\omega_n^{-(n-1)}\}\)?? 代入新多项式，得到的每个数再除以 \(n\)，得到的就是原多项式系数。
其实就是在 FFT 的基础上再进行一次 FFT。
FFT & IFFT：
typedef complex<double> cp;//Complex in STL
const double pi=3.1415926;
int rev[N];
void FFT(comp *f,int n,int inv){//inv=1 -> FFT,inv=-1 -> IFFT
//Bitcount
int bit=0;
while((1<<bit)<n) bit++;
//Butterfly reverse
for(int i=0;i<n;i++){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
if(i<rev[i]) swap(a[i],a[rev[i]]);
}
//FFT/IFFT
for(int mid=1;mid<n;mid<<=1){
cp tmp(cos(pi/mid),inv*sin(pi/mid));
for(int i=0;i<n;i+=2*mid){
cp omega(1,0);
for(int j=0;j<mid;j++,omega*=tmp){
cp x=a[i+j],y=omega*a[i+j+mid];
a[i+j]=x+y;a[i+j+mid]=x-y;
}
}
}
}
- 快速数论变换 (NTT)