单位根定义
方程 \(x^n=1\) 在 \(\mathbb C\) 上根据代数基本定理恰好有 \(n\) 个根，记作 \(\omega_{n},\omega_{n}^2\dots \omega_{n}^n\)。
由于复数相乘的规则是模长相乘，幅角相加，可以看到，这 \(n\) 个根所对应的向量都是单位向量，在复平面上对应着单位圆上的 \(n\) 个等分点。
另一种理解是根据欧拉公式 \(e^{ix}=\cos(x)+i\sin(x)\)。这个公式将 \(\exp\) 函数解析延拓到了复数域上。我们一旦注意到 \(e^{2\pi n}=1\)，就可以推出 \(\omega_{n}=e^{\frac{2\pi i}{n}}=\cos(\frac{2\pi}{n})+i\sin(\frac{2\pi}{n})\)。这带给了我们在 \(\mathbb R\) 上计算单位根的可能性。
根据这个几何意义，我们发现 \(\omega_{n}^{i+n}=\omega_{n}^i\) 是很自然成立的。这意味着单位根和在模 \(n\) 意义下的运算具有很相似的性质。
用上指标来表示单位根的编号也是一个及其明智的选择，我们有 \(\omega_{n}^i=(\omega_{n})^i\)，这也就意味着实际运用时我们往往只需要先求一个单位根再依此推出所有的根。
先求一个根再依此推出所有的根，这令我们回想起数论中我们求最小正原根然后求所有原根的过程。原根也是跟模 \(\varphi(m)\) 意义下的运算有着千丝万缕的联系。
把这两个东西联系起来，单位根有欧拉公式 \(e^{2\pi n}=1\)，原根有欧拉定理 \(g^{\varphi(m)}\equiv 1 \pmod m\)。
相似地，我们可以定义模意义下的单位根 \(\omega_n=g^{\frac{\varphi(m)}{n}}\)。模意义下的 \(n\) 次剩余经常不存在，所以一般只在模数比较特殊（如 \(\texttt{998244353}\)）时使用模意义下的单位根。
DFT 与循环卷积
学习 OI，我们见识了定义在各种各样运算上的“卷积”，以及为了计算这种卷积定义的各种各样的“变换”。
形式化的说对于某种运算 \(\oplus\)，两个序列 \(f,g\) 的 \(\oplus\) 运算卷积得到的结果 \(f*g\) 满足：
\[(f*g)_k=\sum_{i\oplus j=k} f_i g_j \]为了快速计算这种卷积，我们定义线性变换 \(A\) 满足 \(A(f)\cdot A(g)=A(f*g)\)，\(A\) 存在逆 \(A^{-1}\)，且 \(A(f),A^{-1}(f)\) 均可快速计算。
拆开分析 \(A\) 矩阵应该满足性质 \(A_{i,j}A_{i,k}=A_{i,j\oplus k}\)。
当我们将 \(\oplus\) 定义为模 \(n\) 意义下的加法时，\(\omega_n\) 构成的范德蒙德矩阵 \(A_{i,j}=\omega_n^{ij}\) 完美满足了上述条件。此时这个线性变换过程计算的就是 \(f,g\) 的循环卷积。
回顾我们做 \(DFT\) 的实际意义，相当于将 \(\omega\) 带入了多项式 \(F\) 得到点值。
标签：frac,卷积,单位根,oplus,pi,omega,小记 From： https://www.cnblogs.com/yyyyxh/p/unit_root.html