FFT与FWT相关

相关资料:网盘密码wk4r

傅里叶级数:

目的:将一个周期函数分解为无穷个三角函数的和(三角函数的级数),并假设其周期为$2\pi$

形式:$f(x)=\frac{a_0}{2}+\sum_{n=1}^{\infty }(a_ncos(nx)+b_nsin(nx))$

为什么不用管相位:运用三角变换 可将相位分离为sin和cos

前提:三角函数的正交性

在$1,cos(kx),sin(kx)(k\neq 0)$中,任意两个不同函数的积在$[-\pi ,\pi]$上的积分为0,一个函数的平方的积分不为0

证明:利用积化和差公式

$sin\alpha cos\beta=\frac{1}{2}[sin(\alpha +\beta)+sin(\alpha -\beta)]$

$cos\alpha cos\beta=\frac{1}{2}[cos(\alpha +\beta)+cos(\alpha -\beta)]$

$sin\alpha sin\beta=-\frac{1}{2}[cos(\alpha +\beta)-cos(\alpha -\beta)]$

可证得

接下来计算$a_n,b_n$

利用三角函数的正交性可得

$\int _{-\pi}^{\pi}f(x)dx=\int _{-\pi}^{\pi}\frac{a_0}{2}dx=a_0\pi$

$\int _{-\pi}^{\pi}f(x)cos(nx)dx=\int _{-\pi}^{\pi}a_ncos^2(nx)dx=\int _{-\pi}^{\pi}a_n\frac{1+cos(2nx)}{2}dx=a_n\pi$

$\int _{-\pi}^{\pi}f(x)sin(nx)dx=\int _{-\pi}^{\pi}b_nsin^2(nx)dx=\int _{-\pi}^{\pi}b_n\frac{1-cos(2nx)}{2}dx=b_n\pi$

可得

$a_n=\frac{1}{\pi}\int _{-\pi}^{\pi}f(x)cos(nx)dx$

$b_n=\frac{1}{\pi}\int _{-\pi}^{\pi}f(x)sin(nx)dx$

为了方便,我们引入复数

$cosx=\frac{e^{ix}+e^{-ix}}{2}$

$sinx=\frac{e^{ix}-e^{-ix}}{2i}$

可以得到

$f(x)=\frac{a_0}{2}+\sum_{n=1}^{\infty }(a_ncos(nx)+b_nsin(nx))$

$=\frac{a_0}{2}+\sum_{n=1}^{\infty }(a_n\frac{e^{inx}+e^{-inx}}{2}+b_n\frac{e^{inx}-e^{-inx}}{2i})$

$=\frac{a_0}{2}+\sum_{n=1}^{\infty }(\frac{a_n-b_ni}{2}e^{inx}+\frac{a_n+b_ni}{2}e^{-inx})$

因此,取$c_0=\frac{a_0}{2},c_n=\frac{a_n-b_ni}{2},c_{-n}=\frac{a_n+b_ni}{2}(n>0)$

得到$f(x)=\sum^{\infty}_{n=-\infty}c_ne^{inx}$

这看起来就很好看了…

接下来我们再化简一下$c_n$

$c_0=\frac{a_0}{2}=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)dx$

$c_n=\frac{a_n-b_ni}{2}=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)(cos(nx)-isin(nx))dx=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)e^{-inx}dx$

$c_{-n}=\frac{a_n+b_ni}{2}=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)(cos(nx)+isin(nx))dx=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)e^{inx}dx$

其中$n>0$

综上$c_n=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)e^{-inx}dx$

 

到这里我们就总结了傅里叶级数的两个公式

$f(x)=\sum^{\infty}_{n=-\infty}c_ne^{inx}$

$c_n=\frac{1}{2\pi}\int _{-\pi}^{\pi}f(x)e^{-inx}dx$

接下来的内容会很像这两个公式

傅里叶变换

目的:将一个函数分解为三角函数的积分,此函数不需要是周期函数

形式:$f(t)=\int_{-\infty}^{\infty}F(\omega)e^{2\pi i\omega t}d\omega $

形式上和傅里叶级数很像,结果也很像的

先把结果写出来

$F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-2\pi i\omega t}dt$

接下来放证明

$\int_{-\infty}^{\infty}F(\omega)e^{2\pi i\omega t}d\omega$

$=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(x)e^{-2\pi i\omega x}dxe^{2\pi i\omega t}d\omega$

由积分的内外交换的规则可得

$=\int_{-\infty}^{\infty}f(x)\left (\int_{-\infty}^{\infty}e^{2\pi i\omega t}e^{-2\pi i\omega x}d\omega\right )dx$

$=\int_{-\infty}^{\infty}f(x)\left (\int_{-\infty}^{\infty}e^{2\pi i\omega(t-x)}d\omega\right )dx$

$=\int_{-\infty}^{\infty}f(x)\delta (x-t)dx=f(t)$

其中$\delta(x)$的定义为,在$(-\infty,0)\cup (0,\infty)$上的值均为0,$\delta(0)=\infty$且$\delta(x)$在$(-\infty,\infty)$上的积分为1的函数

即$\int_{-\infty}^{\infty}\delta(x)dx=1$

因此严格来讲$\delta(x)$甚至称不上叫一个函数(尽管我不知道这个词什么意思,不过数学上叫它”泛函”)

这里的一个引理$\int_{-\infty}^{\infty}e^{2\pi i \omega t}d\omega =\delta(t)$

在此不作证明,有兴趣可以去有关$\int_{-\infty}^{\infty}e^{2\pi i \omega t}d\omega =\delta(t)$的证明了解一下

$$\begin{cases}&\text F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-2\pi i\omega t}dt\\&\text f(t)=\int_{-\infty}^{\infty}F(\omega)e^{2\pi i\omega t}d\omega\end{cases}$$

其中上面的式子称为傅里叶变换下面的式子称为逆傅里叶变换

上面的式子也有另外的一种表示方式,用$\omega$代替$2\pi\omega$

$$\begin{cases}&\text F(\omega)=\int_{-\infty}^{\infty}f(t)e^{-i\omega t}dt\\&\text f(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{i\omega t}d\omega\end{cases}$$

或者

$$\begin{cases}&\text F(\omega)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t)e^{-i\omega t}dt\\&\text f(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}F(\omega)e^{i\omega t}d\omega\end{cases}$$

也是等价的表现形式,相当于为了将两个式子前面的系数弄成相同的故意将$F(\omega)$乘上$\frac{1}{\sqrt{2\pi}}$

有的时候两个式子上e的指数前面的正负号会在上面的式子里还是下面的式子里也都是可以的,只要保证有且只有一个就行了

离散傅里叶变换

也就是在信息竞赛中最常用的(唯一用到的?)傅里叶变换了

表示为:$F(\omega)=\sum_{t=0}^{n-1}f(t)e^{-\frac{2\pi i \omega t}{n}}$

可得$f(t)=\frac{1}{n}\sum_{\omega=0}^{n-1}F(\omega)e^{\frac{2\pi i \omega t}{n}}$

离散傅里叶变换的证明还是比较简单的

$\frac{1}{n}\sum_{\omega=0}^{n-1}F(\omega)e^{\frac{2\pi i \omega t}{n}}$

$=\frac{1}{n}\sum_{\omega=0}^{n-1}\sum_{x=0}^{n-1}f(x)e^{-\frac{2\pi i\omega x}{n}}e^{\frac{2\pi i \omega t}{n}}$

$=\frac{1}{n}\sum_{\omega=0}^{n-1}\sum_{x=0}^{n-1}f(x)e^{\frac{2\pi i\omega (t-x)}{n}}$

$=\frac{1}{n}\sum_{x=0}^{n-1}f(x)\left (\sum_{\omega=0}^{n-1}e^{\frac{2\pi i\omega (t-x)}{n}}\right )$

我们知道$\sum_{x=0}^{n-1}e^{\frac{2\pi i tx}{n}}=\sum_{x=0}^{n-1}\left (e^{\frac{2\pi i t}{n}}\right )^{x}=0(t\neq 0)$

可以用等比数列求和公式证明

所以当且仅当$t-x =0$的时候$\sum_{\omega=0}^{n-1}e^{\frac{2\pi i\omega (t-x)}{n}}=n$,其余的时候$\sum_{\omega=0}^{n-1}e^{\frac{2\pi i\omega (t-x)}{n}}=0$

所以原式$=\frac{1}{n}f(t)n=f(t)$,证毕

这里$\sum_{\omega=0}^{n-1}e^{\frac{2\pi i\omega (t-x)}{n}}=0(t-x\neq 0)$就等价于在傅里叶变换中$\delta (x)=0(x\neq 0)$的作用

卷积定理

卷积定理是傅里叶变换中最重要的部分,也是为什么我们要使用傅里叶变换的原因

记F[f(t)]表示对f(t)做傅里叶变换后的函数,F[]符号并不是一个函数,而是一个函数的函数

也就是说F[f(t)]表示的不是一个关于t的函数,而是一个关于$\omega$的函数

卷积符号:$(f*g)(t)=\sum_{x}f(x)g(t-x)$这里$\sum_{x}$在不同的傅里叶变换下有不同的含义,在离散傅里叶变换下表示求和,且后面的t-x表示(t-x)mod n的含义(当然是在0~n-1)范围内的,而在傅里叶变换下$\sum_{x}$表示积分,当然后面要乘上一个dx

卷积定理:$F[(f*g)(t)]=F[f(t)]F[g(t)]$

证明不难,无论是利用傅里叶级数中三角函数的正交性,傅里叶变换中$\int_{-\infty}^{\infty}e^{2\pi i \omega t}d\omega =\delta(t)$还是离散傅里叶变换中等比数列求和的定理都可以证明

这里我们就很容易发现一个现象,无论是哪种傅里叶变换,都利用了利用类似于一个函数,只在某种特殊情况下有值的性质,也就是

三角函数的正交性:只有相同的三角函数乘起来再积分有值,不同的乘起来积分=0,在把它均摊到长度$2\pi$的区间上

$\int_{-\infty}^{\infty}e^{2\pi i \omega t}d\omega =\delta(t)$函数:只在t=0的时候有值,为无穷大,再将其均摊到实数域$\mathbb{R}$上就是一个常数了

等比数列求和:当且仅当底数为1的后有值,再均摊到n个数上

FFT的具体计算过程

这里才是唯一重要的东西…其实上面那些对信息竞赛一点都不重要,但是确实很有意思,弄懂还是没有坏处的…(反正迟早要学)

观察卷积的定义,我们发现这个式子很像多项式乘法

$f(x)=\sum_{i=0}^{n}a_ix^i$

$g(x)=\sum_{i=0}^{m}a_ix^i$

$f(x)*g(x)=\sum_{i=0}^{n+m}\sum_{j=0}^{i}a_jb_{i-j}x^i$

因此傅里叶变换的版题就是多项式乘法

注:注意这里的f(x)并不是我们拿去做傅里叶变换的函数f(t),f(t)应当理解为a_i这个数列的函数,即$f(t)|_{t=i}=a_i$才是我们拿去做傅里叶变换的函数

方法就是对系数做离散傅里叶变换后乘起来在做逆离散傅里叶变换变换回去

当然也可以用类似的方法做多项式除法了

注意到在离散傅里叶变换中系数是mod n的,所以为了防止这种情况,我们一般在傅里叶变换时取得模数要大于n+m

具体计算过程也跟多项式有关

观察离散傅里叶变换的式子,相当于我们要求一个函数$f(x)$在$e^{\frac{2\pi ij}{n}}(0\leqslant j<n)$这n个点上的点值

借用这种理解,离散傅里叶变换的卷积定理也会变得很好理解,多项式函数h(x)且$h(x)=f(x)g(x)$则h(x)在系数上就是f(x)和g(x)系数的卷积,且h(x)的傅里叶变换(即h(x)在那n个点上的取值)就是f(x)的傅里叶变换(即f(x)在那n个点上的取值)和g(x)的傅里叶变换(即g(x)在那n个点上的取值)的乘积

快速傅里叶变换的方法如下,要求n为2的幂,当n不是2的幂的时候离散傅里叶变换方法待会再说

观察这个式子

取$\omega=e^{\frac{2\pi i}{n}}$,即$x^n=1$的单位根

$f(\omega^k)=a_0+a_1\omega^k+a_2\omega^{2k}+…+a_{n-1}\omega^{(n-1)k}$

取$f_0(x)=a_0+a_2x+a_4x^2+…+a_{n-2}x^{\frac{n}{2}-1}$

$f_1(x)=a_1+a_3x+a_5x^2+…+a_{n-1}x^{\frac{n}{2}-1}$

则$f(\omega^k)=f_0(\omega^{2k})+\omega^kf_1(\omega^{2k})$

因为注意到$\omega^n=e^{2\pi i}=1,\omega^n=e^{\pi i}=-1$

所以$\omega^{2k}=\omega^{2(k+\frac{n}{2})},\omega^{k}=-\omega^{k+\frac{n}{2}}$

所以无论是多项式的次数上还是需要求得点值数量上,都少了一半,因此递归解决

当递归到n=1的时候就可以直接返回了,结果就是$a_0$

时间复杂度:$T(n)=2T(\frac{n}{2})+O(n)=O(nlogn)$

这里附上代码FFT(cplx a[],int n,bool flag)

其中cplx(complex的缩写)是一个复数类 需要自己手写运算规则,a[0…n-1]和tmp[0…n-1]都是cplx类

rev(x,n)表示将x的前log(n)位翻转,手写

n表示长度,进入时a[0…n-1]存储系数,返回的时候a[0…n-1]存储变换的结果,也就是点值

flag表示方向,flag=1表示离散傅里叶变换,flag=-1表示逆离散傅里叶变换

尽力理解性记忆这种写法

BlueStein

这里介绍一下BlueStein

离散傅里叶变换其实适用的是循环卷积,也就是如果把两个0…n-1的系数都是满的的数列变换了后乘起来再逆变换回去,你得到的是这两个数列的循环卷积,也就是

$c_k=\sum a_ib_j(i+j\equiv k(mod\,n))$

当把n开到两个数列的最大位的两倍以上的时候就可以看做没有循环了

但是有的时候我们需要循环卷积,但是循环位n不是2的幂的时候怎么办呢

BlueStein就是用来干这个的

具体内容看相关资料里的PDF去…讲得很详细了

快速沃尔什变换

这个东西我认了…我搞不懂沃尔什级数究竟是个什么…

所以这里只能简单讲一讲了…

扩展的卷积定义

$c_k=\sum a_ib_j(i\oplus j=k)$

FWT就是来解决当$\oplus$是位运算的时候的卷积的,依然满足卷积定理,依然要求n为2的幂(你问n不是2的幂的时候怎么办?那作位运算不就不封闭了吗…)

记$A$为一个数列$a_0,a_1,…,a_{n-1}$

记$A_0$为数列A的前半部分,即$a_0,a_1,…,a_{\frac{n}{2}-1}$

记$A_1$为数列A的后半部分,即$a_{\frac{n}{2}},a_{\frac{n}{2}+1},…,a_{n-1}$

记$A=(A_0,A_1)$表示把一个两数列拼接起来

记$A+B,A-B,A\times B$表示两个数列的每一个位置依次加减或者乘得到的数列

显然$A\pm B=(A_0\pm B_0,A_1\pm B_1),A\times B=(A_0\times B_0,A_1\times B_1)$

记$A\oplus B$表示数列A,B的位运算卷积,位运算卷积显然是满足加减法的分配律的

即$A\oplus(B\pm C)=(A\oplus B)\pm(A\oplus C)$

无论什么情况下 如果数列A中n=1,则FWT(A)=A

因为0 xor 0=0 and 0=0 or 0=0

当$\oplus$是异或的时候

$FWT(A)=(FWT(A_0+A_1),FWT(A_0-A_1))\\FWT^{-1}(A)=(FWT^{-1}(\frac{A_0+A_1}{2}),FWT^{-1}(\frac{A_0-A_1}{2}))$

当$\oplus$是与的时候

$FWT(A)=(FWT(A_0+A_1),FWT(A_1))\\FWT^{-1}(A)=(FWT^{-1}(A_0-A_1),FWT^{-1}(A_1))$

当$\oplus$是或的时候

$FWT(A)=(FWT(A_0),FWT(A_1+A_0))\\FWT^{-1}(A)=(FWT^{-1}(A_0),FWT^{-1}(A_1-A_0))$

显然$FWT(A+B)=FWT(A)+FWT(B)$

我们只需要证明

(1)$FWT^{-1}(FWT(A))=A$

(2)$FWT(A\oplus B)=FWT(A)\times FWT(B)$

就行了…

(1)显然…观察一下FWT和逆FWT式子之间的关系就行了…

(2)

这里证明一下$\oplus$是与的时候的情况…

$FWT(A\& B)=FWT(A)FWT(B)$

证明如下:采用数学归纳法

$FWT(A\& B)=FWT((A_0\& B_0+A_1\& B_0+A_0\& B_1,A_1\& B_1))$

将A,B的第一位分类,分解为前半部分和后半部分,以展开A&B

$=(FWT(A_0\& B_0+A_1\& B_0+A_0\& B_1+A_1\& B_1),FWT(A_1\& B_1))$

FWT的定义

$=(FWT((A_0+A_1)\& (B_0+B_1)),FWT(A_1\& B_1))$

位运算卷积的分配率

$=(FWT(A_0+A_1)\times FWT(B_0+B_1),FWT(A_1)\times FWT(B_1))$

递归证明

$=(FWT(A_0+A_1),FWT(A_1))\times (FWT(B_0+B_1),FWT(B_1))$

数列的基本性质$A\times B=(A_0\times B_0,A_1\times B_1)$

$=FWT(A)\times FWT(B)$

FWT的定义

证毕…

$\oplus$是异或的情况在相关资料里的快速沃尔什变换的那个PDF里有…

$\oplus$是或的情况自己证明吧,跟与差不多…

发表评论

电子邮件地址不会被公开。 必填项已用*标注