任意长度循环卷积&单位根反演 学习笔记

今天听 myee" role="presentation" style="position: relative;">myee$\mathtt{\text{m}}\mathtt{\text{yee}}$ 嘴的，赶紧来补个学习笔记。

PS：FFT 本质是长度为 2k" role="presentation" style="position: relative;">2k$2^k$ 的循环卷积。

单位根反演

反演本质：

1n∑i=0n−1ωnai=[n|a]" role="presentation" style="text-align: center; position: relative;">1n∑i=0n−1ωain=[n|a]$$\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ai}=[n|a]$$

证明：

• 如果 n|i" role="presentation" style="position: relative;">n|i$n|i$，那么显然可以将 a" role="presentation" style="position: relative;">a$a$ 拆为若干个 ωnn" role="presentation" style="position: relative;">ωnn${\omega }_n^n$，之后式子只剩下了 n" role="presentation" style="position: relative;">n$n$ 个 ωnn" role="presentation" style="position: relative;">ωnn${\omega }_n^n$，那么乘上 1n" role="presentation" style="position: relative;">1n$\frac{1}{n}$ 就是 1" role="presentation" style="position: relative;">1$1$ 啦。
• 如果 n⧸|a" role="presentation" style="position: relative;">n/|a$n\text{⧸}|a$，容易发现 ωni" role="presentation" style="position: relative;">ωin${\omega }_n^i$ 还是能够互相抵消，那么等于 0" role="presentation" style="position: relative;">0$0$。

形式：

gk=∑i=0n−1fiωnik⇔fk=1n∑i=0n−1giωnik" role="presentation" style="text-align: center; position: relative;">gk=∑i=0n−1fiωikn⇔fk=1n∑i=0n−1giωikn$$g_k=\sum _{i=0}^{n-1}{f}_i{\omega }_n^{ik}\iff f_k=\frac{1}{n}\sum _{i=0}^{n-1}{g}_i{\omega }_n^{ik}$$

循环卷积

定义 k" role="presentation" style="position: relative;">k$k$ 阶循环卷积为：

hk=∑i+j≡k(modn)fi×gj" role="presentation" style="text-align: center; position: relative;">hk=∑i+j≡k(modn)fi×gj$$h_k=\sum _{i+j\equiv k(\mathrm{mod}n)}{f}_i\times g_j$$

可以写出二阶循环卷积(不就是异或吗)的转移矩阵：

fwt=[111−1]ifwt=[111−1]" role="presentation" style="text-align: center; position: relative;">fwt=[111−1]ifwt=[111−1]$$fwt=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]ifwt=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$$

k" role="presentation" style="position: relative;">k$k$ 阶的转移矩阵是这样的：

fwt=[ωk0ωk0ωk0⋯ωk0ωk0ωk1ωk2⋯ωkk−1ωk0ωk2ωk4⋯ωk2k−2⋮⋮⋮⋱⋮ωk0ωkk−1ωk2k−1⋯ωkk2−2k+1]ifwt=[ωk−0ωk−0ωk−0⋯ωk−0ωk−0ωk−1ωk−2⋯ωk−k+1ωk−0ωk−2ωk−4⋯ωk−2k+2⋮⋮⋮⋱⋮ωk−0ωk−k+1ωk−2k+1⋯ωk−k2+2k−1]" role="presentation" style="position: relative;">fwt=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢ω0kω0kω0k⋮ω0kω0kω1kω2k⋮ωk−1kω0kω2kω4k⋮ω2k−1k⋯⋯⋯⋱⋯ω0kωk−1kω2k−2k⋮ωk2−2k+1k⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥ifwt=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢ω−0kω−0kω−0k⋮ω−0kω−0kω−1kω−2k⋮ω−k+1kω−0kω−2kω−4k⋮ω−2k+1k⋯⋯⋯⋱⋯ω−0kω−k+1kω−2k+2k⋮ω−k2+2k−1k⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥$$fwt=\left[\begin{array}{ccccc}{\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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\omega }_k^0& {\omega }_k^{k-1}& {\omega }_k^{2k-1}& \cdots & {\omega }_k^{k^2-2k+1}\end{array}\right]ifwt=\left[\begin{array}{ccccc}{\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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\omega }_k^{-0}& {\omega }_k^{-k+1}& {\omega }_k^{-2k+1}& \cdots & {\omega }_k^{-k^2+2k-1}\end{array}\right]$$

这样可以 O(k2)" role="presentation" style="position: relative;">O(k2)$\mathcal{O}\mathcal{(}{\mathcal{k}}^{\mathcal{2}}\mathcal{)}$ 地完成 fwt 变换(但板题 任意模数 Chirp Z-Transform 需要用 FFT 优化加速)，O(k)" role="presentation" style="position: relative;">O(k)$\mathcal{O}\mathcal{(}\mathcal{k}\mathcal{)}$ 地点乘。

PS：如果需要将对应系数相加，可以在 fwt 后直接相加减，因为这是个线性变换。

咕咕咕

P4191 [CTSC2010]性能优化