• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

FWT简介(洛谷P4717)

用途

Fast Walsh-Hadamard Transform,即FWT,用来解决形如ci=∑j⊕k=iajbkci=∑j⊕k=iajbk一类的卷积,其中⊕⊕表示位运算(xor/or/andxor/or/and)。

过程

类比FFT,我们可以构造出一个变换使得aiai和bjbj可以直接相乘,再变换回来求得答案。同样的,FWT也分DWT和IDWT两步。

DWT

设DWT(a)iDWT(a)i表示aa经过DWT之后的变换。那么我们可以得到
DWT(a)i=∑j=0n−1ajf(i,j)DWT(a)i∗DWT(b)i=DWT(c)i①②(61)(62)
(61)DWT(a)i=∑j=0n−1ajf(i,j)①(62)DWT(a)i∗DWT(b)i=DWT(c)i②

其中f(i,j)f(i,j)表示变换的系数。把①式代入②中,可以发现f(i,j)∗f(i,k)=f(i,j⊕k)f(i,j)∗f(i,k)=f(i,j⊕k)
对于不同的位运算,变换是不同的。下面给出结论:

⊕=&:f(i,j)=[i&j=i]⊕=&:f(i,j)=[i&j=i]

⊕=|:f(i,j)=[i&j==j]⊕=|:f(i,j)=[i&j==j]

⊕=^:f(i,j)=(−1)cnt(i&j)⊕=^:f(i,j)=(−1)cnt(i&j)

(cnt(i)cnt(i))表示ii在二进制下1的个数。

YY一下很对啊,但是不知道它怎么来的啊。

因为位运算每一位的独立性,f(i,j)f(i,j)可以二进制拆分。那么我们就可以开始推式子了:
DWT(a)i=∑j=0n−1ajf(i,j)=∑j=0n2−1ajf(i,j)+∑j=n2n−1ajf(i,j)=f(i0,0)∑j=0n2−1ajf(i1−>l−1,j1−>l−1)+f(i0,1)∑j=n2n−1ajf(i1−>l−1,j1−>l−1)(63)(64)(65)
(63)DWT(a)i=∑j=0n−1ajf(i,j)(64)=∑j=0n2−1ajf(i,j)+∑j=n2n−1ajf(i,j)(65)=f(i0,0)∑j=0n2−1ajf(i1−>l−1,j1−>l−1)+f(i0,1)∑j=n2n−1ajf(i1−>l−1,j1−>l−1)

然后就变成
DWT(A)i=f(0,0)DWT(AL)i+f(0,1)DWT(AR)iDWT(A)i+n2=f(1,0)DWT(AL)i+f(1,1)DWT(AR)i
DWT(A)i=f(0,0)DWT(AL)i+f(0,1)DWT(AR)iDWT(A)i+n2=f(1,0)DWT(AL)i+f(1,1)DWT(AR)i

递归做就好了。(实际上并不用递归,和FFT一样迭代即可)

IDWT

代回去之后发现解个二元一次方程就好了。

模板


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址