第一次用博客园写学习笔记，写的不好请见谅~
欢迎各位OIer在评论区说一下自己对这篇博客的建议！
有关多项式的基本概念
对于求和式 \(\sum a_nx^n\) ，如果是有限项相加，称为多项式，记作 \(f(x)=\sum_{k=0}^n a_kx^k\)。
一个多项式的度（也称次数）就是这个多项式最高次项的次数，记作 \(\deg f\) 。
多项式的导数具有以下公式：
\[\left(\sum_{k=0}^{+\infty}a_kx^k\right)'=\sum_{k=1}^{+\infty}ka_kx^{k-1} \]定义加法和乘法以后，多项式的基本运算和整数基本一致。
多项式的表示一般有两种方法：
- 系数表示，就是形如 \(f(x)=\sum_{k=0}^n a_kx^k\) 的形式。
- 点值表示，即给出 \(n+1\) 个点 \((x_{0}, y_{0}), (x_{1}, y_{1}), \dots, (x_{n}, y_{n})\) ，求一个 \(n\) 次多项式使得这 \(n+1\) 个点都在 \(f(x)\) 上。
快速傅里叶变换（FFT）
一种快速多项式乘法的方法。
单位根
前置知识：复数
顾名思义，单位根就是满足 \(x^n=1\) 的根。
众所周知，在复数域内， \(n\) 次多项式有 \(n\) 个根，因此 \(x^n=1\) 也有 \(n\) 个根，一般把第 \(k\) 个根记作 \(\omega_n^k\) 。
由于复数乘法的几何意义是模长相乘，辐角相加，因此 \(\omega_n^k\) 的模长一定为 \(1\) ，辐角为 \(\frac{2\pi}{n}\) 的倍数。
为方便，我们设 \(\omega_n^k\) 的辐角为 \(\frac{2k\pi}{n}\) ，或者 \(\frac{360^\circ k}{n}\) 。
单位根有三个重要的性质。对于任意正整数 n 和整数 k：
\[\begin{aligned} \omega_n^n&=1\\ \omega_n^k&=\omega_{xn}^{xk}\\ \omega_{2n}^{k+n}&=-\omega_{2n}^k\\ \end{aligned} \]这三个性质在快速傅里叶变换中会得到应用。
DFT
又称离散傅里叶变换、Discrete Fourier Transform。
DFT的思想是将两个多项式的系数表示与点值表示互相转化。
因为多项式的系数表示直接相乘是 \(O(n^2)\) 的，而点值表示相乘是 \(O(n)\) 的。（只需要把每个点处的值相乘）
先考虑将系数表示转化为点值。
如果暴力去求，时间复杂度还是 \(O(n^2)\) 的。
那这个时候我们就要用到一个东西叫做：
FFT
又称快速傅里叶变换、Fast (Discrete) Fourier Transform。
开个坑，以后再写。
标签：多项式,sum,相乘,笔记,算法,傅里叶,kx,omega From： https://www.cnblogs.com/SqrtSecond/p/17129409.html