简约 网站模板,电商网站推广方法,软件app定制开发,做网站制作一般多少钱今天听 \(\texttt{m}\color{red}{\texttt{yee}}\) 嘴的#xff0c;赶紧来补个学习笔记。 PS#xff1a;FFT 本质是长度为 \(2^k\) 的循环卷积。 单位根反演 反演本质#xff1a; \[\frac1n\sum_{i0}^{n-1}\omega_{n}^{ai}[n|a] \]证明#xff1a; 如果 \(n|i\)#xff0c;… 今天听 \(\texttt{m}\color{red}{\texttt{yee}}\) 嘴的赶紧来补个学习笔记。 PSFFT 本质是长度为 \(2^k\) 的循环卷积。 单位根反演 反演本质 \[\frac1n\sum_{i0}^{n-1}\omega_{n}^{ai}[n|a] \]证明 如果 \(n|i\)那么显然可以将 \(a\) 拆为若干个 \(\omega_n^n\)之后式子只剩下了 \(n\) 个 \(\omega_{n}^{n}\)那么乘上 \(\frac1n\) 就是 \(1\) 啦。如果 \(n\not|a\)容易发现 \(\omega_n^{i}\) 还是能够互相抵消那么等于 \(0\)。 形式 \[g_k\sum_{i0}^{n-1}f_{i}\omega_{n}^{ik}\Leftrightarrow f_k\frac1n\sum_{i0}^{n-1}g_i\omega_n^{ik} \]循环卷积 定义 \(k\) 阶循环卷积为 \[h_k\sum_{ij\equiv k\pmod{n}}f_i\times g_j \]可以写出二阶循环卷积(不就是异或吗)的转移矩阵 \[fwt\begin{bmatrix}11\\1-1\end{bmatrix}ifwt\begin{bmatrix}11\\1-1\end{bmatrix} \]\(k\) 阶的转移矩阵是这样的 \[fwt\begin{bmatrix}\omega_k^0\omega_k^0\omega_k^0\cdots\omega_k^0\\\omega_k^0\omega_k^1\omega_k^2\cdots\omega_k^{k-1}\\\omega_k^0\omega_k^2\omega_k^4\cdots\omega_k^{2k-2}\\\vdots\vdots\vdots\ddots\vdots\\\omega_k^0\omega_k^{k-1}\omega_k^{2k-1}\cdots\omega_k^{k^2-2k1}\end{bmatrix}ifwt\begin{bmatrix}\omega_k^{-0}\omega_k^{-0}\omega_k^{-0}\cdots\omega_k^{-0}\\\omega_k^{-0}\omega_k^{-1}\omega_k^{-2}\cdots\omega_k^{-k1}\\\omega_k^{-0}\omega_k^{-2}\omega_k^{-4}\cdots\omega_k^{-2k2}\\\vdots\vdots\vdots\ddots\vdots\\\omega_k^{-0}\omega_k^{-k1}\omega_k^{-2k1}\cdots\omega_k^{-k^22k-1}\end{bmatrix} \]这样可以 \(\mathcal{O(k^2)}\) 地完成 fwt 变换(但板题 任意模数 Chirp Z-Transform 需要用 FFT 优化加速)\(\mathcal{O(k)}\) 地点乘。 PS如果需要将对应系数相加可以在 fwt 后直接相加减因为这是个线性变换。 咕咕咕 P4191 [CTSC2010]性能优化
