符号表
- \(\mathbb{A}\) 多项式, 最高次数为 \(n-1(n=2^{k})\), 系数表示为 \(a_{i}x^{i}\)
- \(\mathbb{A}(x)\) 多项式 \(\mathbb{A}\) 在 \(x\) 处的点值
- \({_{0}\mathbb{A}}, {_{1}\mathbb{A}}\) 多项式 \(\mathbb{A}\) 的偶数次项和奇数次项
- \(\mathbb{A} \circ \mathbb{B}\) 将两个多项式对应位进行 \(\circ\) (加 \(+\), 减 \(-\), 乘 \(*\)) 操作 (系数表示为 \(a_{i}\circ b_{i}\))
- \(\mathbb{A} \circ \mathbb{B}\) 将两个多项式进行 \(\circ\) (乘 \(\times\), 异或 \(\oplus\), 或 \(\&\), 与 \(|\)) 卷积
- \((\mathbb{A}, \mathbb{B})\) 将两个多项式进行拼接操作
- \(\mathcal{F}, \mathcal{F}^{-1}\) 快速傅里叶变换及其逆变换
- \(\mathcal{N}, \mathcal{N}^{-1}\) 快速数论变换及其逆变换
- \(\mathcal{W}, \mathcal{W}^{-1}\) 快速沃尔什变换及其逆变换
- \(\mathcal{M}, \mathcal{M}^{-1}\) 快速莫比乌斯变换及其逆变换
FFT和NTT
我们知道, 多项式乘法在系数表示中实质上就是在求卷积, 而FFT和NTT就是常见的用于计算卷积的算法.
\(\mathcal{F}\) 和 \(\mathcal{F}^{-1}\) 以及 \(\mathcal{N}\) 和 \(\mathcal{N}^{-1}\) 的物理意义暂且不谈, 在多项式中, 它们所实现的都是系数表示和点值表示之间的相互转换. 这和多项式乘法又有什么关系呢? 因为有 \((\mathbb{A}\times\mathbb{B})(x)=\mathbb{A}(x)\times\mathbb{B}(x)\), 所以只要有足够多的点值相乘, 再用逆运算转换回系数表示就实现了多项式乘法.
FFT
FFT利用了单位根在复数域上的特殊性质加速傅里叶变换.
单位根
单位根 \(\omega_{n}^{k}\) 的辐角为 \(\frac{2\pi}{n}\times k\), 因此 \(\omega_{n}^{k}=\cos{\frac{2k\pi}{n}}+i\cdot\sin{\frac{2k\pi}{n}}\) , 它被称为 \(k\) 次单位根
单位根有如下性质:
- \(\forall i \neq j, \omega_{n}^{i}\neq\omega_{n}^{j}\), 这为我们点值表示选点带来了方便
- \(\omega_{n}^{0}=\omega_{n}^{n}=1\)
- \(\omega_{2n}^{2k}=\omega_{n}^{k}\)
- \(\omega_{n}^{k+\frac{\pi}{2}}=-\omega_{n}^{k}\)
傅里叶变换
\[ \begin{align*} \mathbb{A}(x) &=a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1} \\ &=(a_{0}+a_{2}x^{2}+\cdots+a_{n-2}x^{n-2})+x(a_{1}+a_{3}x^{2}+\cdots+a_{n-1}x^{n-2}) \\ &={_{0}\mathbb{A}(x^{2})}+x\cdot{_{1}\mathbb{A}(x^{2})} \end{align*} \]
将 \(x=\omega_{n}^{k}\) 代入:
- \(k\in [0, \frac{n}{2}-1]\) 时: \[ \begin{align*} \mathbb{A}(\omega_{n}^{k})&={_{0}\mathbb{A}((\omega_{n}^{k})^{2})}+\omega_{n}^{k}\cdot{_{1}\mathbb{A}((\omega_{n}^{k})^{2})} \\ &={_{0}\mathbb{A}(\omega_{n}^{2k})}+\omega_{n}^{k}\cdot{_{1}\mathbb{A}(\omega_{n}^{2k})} \\ &={_{0}\mathbb{A}(\omega_{\frac{n}{2}}^{k})}+\omega_{n}^{k}\cdot{_{1}\mathbb{A}(\omega_{\frac{n}{2}}^{k})} \end{align*} \]
- \(k\in [\frac{n}{2}, n-1]\) 时, 令 \(k^{'}=k-\frac{n}{2}\) \[ \begin{align*} \mathbb{A}(\omega_{n}^{k})&=\mathbb{A}(\omega_{n}^{k^{'}+\frac{n}{2}})\\ &={_{0}\mathbb{A}(\omega_{\frac{n}{2}}^{k^{'}})}-\omega_{n}^{k^{'}}\cdot{_{1}\mathbb{A}(\omega_{\frac{n}{2}}^{k^{'}})} \end{align*} \]
这样就能分治下去求解了
傅里叶逆变换
\[a_{k}=\sum_{i=0}^{n-1}\mathbb{A}(\omega_{n}^{i})(\omega_{n}^{-k})^{i}\] 是不是和求点值很像: \[\mathbb{A}(\omega_{n}^{k})=\sum_{i=0}^{n-1}a_{i}(\omega_{n}^{k})^{i}\]
因此套用傅里叶变换的过程, 并用 \(\omega_{n}^{-k}\) 替换 \(k\) 次单位根就实现了傅里叶逆变换.
NTT
NTT实质上就是用与单位根性质相似的原根来加速模意义下傅里叶变换过程的算法.
若模数是奇素数 \(p=qn+1,(n=2^{m})\), 其原根为 \(g\), 设 \(\mathbf{N}=p-1=\varphi(p)\)
用 \(g_{n}^{1}=g^{\frac{N}{n}}=g^{q} \pmod{p}\) 等价 \(\omega_{n}^{1}\)
则有如下性质:
- \(\forall i \neq j, g_{n}^{i}\neq g_{n}^{j}\)
- \(g_{n}^{0} \equiv g_{n}^{n} \equiv 1 \pmod{p}\)
- \(\omega_{n}^{k}=\omega_{\frac{n}{2}}^{\frac{k}{2}}\)
- \(g_{n}^{k+\frac{n}{2}}=-g_{n}^{k}\)
类似于FFT, 用 \(g_{n}^{1}\)替换单位根并注意取模就可以了.
FWT和FMT
还没学会, 未完待续.