卷积全家桶
FFT 快速傅里叶变换
应用场景:
有\(2^n-1\)次多项式\(f(x),g(x)\),求多项式\(f(x)g(x)\)的各项系数.
换言之,有长为\(2^n\)数组\(f,g\),(下标从\(0\)开始),求长为\(2^{n+1}-1\)数组\(h\)满足\(h_i=\sum_{j=0}^{i}f_jg_{i-j}\)(超出\(f,g\)下标范围的地方用\(0\)补全).
在下面的推导中,我们用\(n\)代替\(2^n\).约定用\(f_i\)表示多项式\(f\)的\(i\)次项系数,\(f(x)\)表示在\(x\)处多项式\(f\)的值.
单位根及其性质
让我们考察方程\(x^n=1\)的解的特点.注意到在实数域内解的性质随\(n\)的变化千奇百怪,因此我们在复数域内考虑这个问题.我们用模长和幅角去描述一个复数,就可以注意到\(|x|=1,n\theta=2k\pi(k\in \mathbb{Z})\),为了简便,我们约定\(k=1\),这样我们发现\(x=e^{i\frac{2\pi}{n}}=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}\)是最简便的一个解.
我们定义\(n\)阶单位根\(\omega_n=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}\).
性质1:由定义,发现\(\omega_1^1=1,\omega_2^1=-1\).
性质2:由定义,发现\(\omega_n^k=e^{\frac{2\pi k}{n}i}\)只与\(\frac{k}{n}\)有关,因此\(\omega_{pn}^{pk}=\omega_n^k\).
性质3:由于在复数坐标系中,\(\omega_n^0,\omega_n^1,\dotsi,\omega_n^{n-1}\)的终点成一个正多边形,由对称性,这些向量的和为零向量.也即:\(\sum_{i=0}^{n-1}\omega_n^i=0\)
FFT/IFFT 的过程
我们设\(\text{FFT}(f)_i=f(\omega_n^i)\).我们将\(f\)按照下标的奇偶性分成两半:
\[\begin{align} f(\omega_n^i) & =f_0\omega_n^{0*i}+f_1\omega_n^{1*i}+f_2\omega_n^{2*i}+\dotsi +f_{n-2}\omega_n^{(n-2)*i}+f_{n-1}\omega_n^{(n-1)*i} \notag \\ & =(f_0\omega_n^{0*i}+f_2\omega_n^{2*i}+\dotsi +f_{n-2}\omega_n^{(n-2)*i})+(f_1\omega_n^{1*i}+f_3\omega_n^{3*i}+\dotsi+f_{n-1}\omega_n^{(n-1)*i}) \notag \\ & = (f_0\omega_n^{0*i}+f_2\omega_n^{2*i}+\dotsi +f_{n-2}\omega_n^{(n-2)*i})+\omega_n^{i}(f_1\omega_n^{0*i}+f_3\omega_n^{2*i}+\dotsi+f_{n-1}\omega_n^{(n-2)*i}) \notag \\ & = (f_0\omega_\frac{n}{2}^{0*i}+f_2\omega_\frac{n}{2}^{1*i}+\dotsi +f_{n-2}\omega_\frac{n}{2}^{(\frac{n}{2}-1)*i})+\omega_n^{i}(f_1\omega_\frac{n}{2}^{0*i}+f_3\omega_\frac{n}{2}^{1*i}+\dotsi+f_{n-1}\omega_\frac{n}{2}^{(\frac{n}{2}-1)*i}) \notag \\ & = f_L(\omega_\frac{n}{2}^i)+\omega_n^{i}f_R(\omega_\frac{n}{2}^i) \notag \\ \end{align} \]则有:
\[f(\omega_n^i) = f_L(\omega_\frac{n}{2}^i)+\omega_n^{i}f_R(\omega_\frac{n}{2}^i) (i<\frac{n}{2}) \\ f(\omega_n^i) = f_L(\omega_\frac{n}{2}^{i-\frac{n}{2}})-\omega_n^{i-\frac{n}{2}}f_R(\omega_\frac{n}{2}^{i-\frac{n}{2}}) (i\geq \frac{n}{2}) \\ \]观察到这是一个分治结构,因此我们可以递归解决这个问题,也可以倍增的迭代式解决问题.
由多项式乘法定义,不难观察到:
\[\text{FFT}(h)_i=h(\omega_n^i)=f(\omega_n^i)g(\omega_n^i)=\text{FFT}(f)_i\text{FFT}(g)_i \]也就是说,我们把\(f\)和\(g\)做FFT的结果对应相乘,就能得到\(h\)的FFT.那么如何通过\(\text{FFT}(h)\)还原回\(h\)呢?
我们用矩阵考虑这个问题.我们把一个多项式\(f\)的系数和\(\text{FFT}(f)\)的结果都描述为一个列向量,令矩阵\(A\)为\(n\)阶方阵,且\(A_{i,j}=\omega_n^{ij}\),发现:\(\text{FFT}(f)=A*\mathbb{f}\). 因此,我们只要找出\(A\)的逆矩阵\(A^{-1}\),就可以实现IFFT.
给出结论:若\(B_{i,j}=\frac{\omega_n^{-ij}}{n}\),则\(A*B=I_n\).证明:
\[\begin{align} (A*B)_{i,j} & =\sum_{k=0}^{n-1}A_{i,k}B_{k,j} \notag \\ & = \sum_{k=0}^{n-1}\omega_n^{ik}\frac{\omega_n^{-kj}}{n} \notag \\ & = \frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{(i-j)k} \notag \\ \end{align} \]我们发现,上面式子当\(i=j\)时,\((A*B)_{i,j}\)显然为\(1\),余下情况中,我们不妨设\(m=i-j(i>j)\)
\[\begin{align} (A*B)_{i,j} & = \frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{(i-j)k} \notag \\ & = \frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{mk \mod n} \notag \\ & = \frac{(m,n)}{n} \sum_{k=0}^{\frac{n}{(m,n)} -1}\omega_{\frac{n}{(m,n)}}^{k} \notag \\ & = 0 \notag \\ \end{align} \]综上,\((A*B)_{i,j}=[i=j],B=A^{-1}\).实际上,我们可以忽略掉矩阵中除以\(n\)的系数,在最后的结果处除以\(n\)即可.
\[\begin{align} \text{IFFT}(f)_i & =f_0\omega_n^{-0*i}+f_1\omega_n^{-1*i}+f_2\omega_n^{-2*i}+\dotsi +f_{n-2}\omega_n^{-(n-2)*i}+f_{n-1}\omega_n^{-(n-1)*i} \notag \\ & =(f_0\omega_n^{-0*i}+f_2\omega_n^{-2*i}+\dotsi +f_{n-2}\omega_n^{-(n-2)*i})+(f_1\omega_n^{-1*i}+f_3\omega_n^{-3*i}+\dotsi+f_{n-1}\omega_n^{-(n-1)*i}) \notag \\ & = (f_0\omega_n^{-0*i}+f_2\omega_n^{-2*i}+\dotsi +f_{n-2}\omega_n^{-(n-2)*i})+\omega_n^{-i}(f_1\omega_n^{-0*i}+f_3\omega_n^{-2*i}+\dotsi+f_{n-1}\omega_n^{-(n-2)*i}) \notag \\ & = (f_0\omega_\frac{n}{2}^{-0*i}+f_2\omega_\frac{n}{2}^{-1*i}+\dotsi +f_{n-2}\omega_\frac{n}{2}^{-(\frac{n}{2}-1)*i})+\omega_n^{-i}(f_1\omega_\frac{n}{2}^{-0*i}+f_3\omega_\frac{n}{2}^{-1*i}+\dotsi+f_{n-1}\omega_\frac{n}{2}^{-(\frac{n}{2}-1)*i}) \notag \\ & = \text{IFFT}(f_L)_i + \omega_n^{-i}*\text{IFFT}(f_R)_i \notag \\ \end{align} \]则有:
\[\text{IFFT}(f)_i= \text{IFFT}(f_L)_i + \omega_n^{-i}*\text{IFFT}(f_R)_i \ \ (i<\frac{n}{2}) \\ \text{IFFT}(f)_i= \text{IFFT}(f_L)_{i-\frac{n}{2}} - \omega_n^{-(i-\frac{n}{2})}*\text{IFFT}(f_R)_{i-\frac{n}{2}} \ \ (i\geq\frac{n}{2}) \]这与FFT有类似的分治结构,我们只需要把系数取倒数,最后结果除以\(n\)即可,总复杂度\(O(n \log n)\).
FWT 快速沃尔什变换
有时我们需要对下标做位运算的卷积,也即:
\[h_i=\sum_{p\oplus q=i}f_pg_q \]其中\(\oplus\)可以是按位或,按位与,按位异或中的一种.
与FFT的想法类似,我们数列到数列的映射\(\text{FWT}\),使得对任意\(i\in[0,n)\)有\(\text{FWT}(h)_i=\text{FWT}(f)_i\text{FWT}(g)_i\)成立.
对于或运算而言,我们构造\(\text{FWT}(f)_i=\sum_{j\in i}f_j\)即可.
对于与运算而言,我们构造\(\text{FWT}(f)_i=\sum_{i\in j}f_j\)即可.
对于异或运算而言,我们构造\(\text{FWT}(f)_i=\sum_{j = 0}^{n-1}f_j*(-1)^{\#(i\&j)}\)即可.
我们按照实际含义去思考如何递归处理FWT和IFWT都是不难的.
我们也可以从递归时前/后半段结果对答案贡献时的矩阵来考虑FWT.可以证明,只需构造一个\(2\times2\)的矩阵\(c\)使得\(c_{i,j\oplus k}=c_{i,j}c_{i,k}\),且\(c\)的逆矩阵存在即可,这种方法不多赘述.
子集卷积
有时我们需要解决\(h_i=\sum_{(p \cup q = i) \wedge (p \cap q = \emptyset)}f_pg_q\),发现交集为空并不好做,但是发现\((p \cup q = i) \wedge (p \cap q = \emptyset) \Leftrightarrow (p \cup q = i) \wedge \#\{p\}+\#\{q\}=\#\{i\}\)
,就可以想到从集合大小的角度来解决问题.我们构造\(FWT_k(h)_i=\sum_{j\in i \wedge\#\{j\}=k}h_j\),就可以发现\(FWT_k(h)_i=FWT_k(f)_iFWT_k(g)_i\)类似前面做卷积就可以了,复杂度\(O(n\log^2n)\).
NTT 快速数论变换
有时我们需要解决FFT的问题,但是我们又对精度有要求/需要在模意义下解决问题时,就需要使用NTT.
实际上,浮点数运算是复数不可避免的问题,那我们需要构造一个什么样的\(\omega\)呢?
我们约束模数是一个质数\(p\).我们需要构造一个\(\omega_n\)使得\(\omega_n^i \mod p\)各不相同(\(i\in[0,n)\)),并且\(\omega_n^n \equiv 1 \mod p\)成立.考虑到上述第一个条件,我们去考虑原根\(g\).由于\(g^{p-1} \equiv 1\)成立,因此我们需要让\(\omega_n=g^{\frac{p-1}{n}}\),替换掉FFT中的单位根就可以解决问题了.
由于上式中需要有\(n | (p-1)\)成立,而\(n=2^l\),因此\(p-1\)中需要含有较多质因子\(2\).因此有一些质数是不适合作为NTT模数的.
\(p=998244353=119*2^{23}+1,g=3\)是一组常见的质数/原根.
标签：dotsi,frac,卷积,text,FFT,全家,notag,omega From： https://www.cnblogs.com/snowycat1234/p/18341921