FFT

快速傅里叶变换 (Fast Fourier Transform), 即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。 在算法竞赛中,FFT主要用于解决卷积的加速与优化,最典型的例子是求两个多项式的乘积。 譬如说 \[f(x)=a_{0}x^{0}+a_{1}x^{1}+...+a_{n-1}x^{n-1}\] \[g(x)=b_{0}x^{0}+b_{1}x^{1}+...+b_{n-1}x^{n-1}\] 求\(f(x)g(x)\) 如果用传统思路去解决这个问题,显然再怎么优化似乎只能到\(\Theta(n^{2})\)的复杂度。因为不管如何考虑,枚举偏序对\((a_{i},b_{j})\)的过程似乎都没有任何的冗余。如果我们不能跳出以上思维的局限,我们就不可能在根本上降低算法的时间复杂度。 让我们首先换一个角度来考察多项式。     Read more
tigertang's avatar
tigertang Feb 20, 2017

莫比乌斯反演

定理:设\(F(n)\)和\(f(n)\)是定义在非负整数集合上的两个函数,并且满足条件\(F(n)=\sum_{d|n}f(d)\),则我们得到结论\(f(n)=\sum_{d|n}\mu (d)F(\frac{n}{d})\)。 先介绍一下\(\mu(d)\)函数: \[ \mu(d)=\left\{\begin{matrix}1&d=1\\ (-1)^{k}&d=p_{1}p_{2}...p_{k}\\\ 0&otherwise \end{matrix}\right. \]     Read more
tigertang's avatar
tigertang Feb 13, 2017