今天学习了一下FWT……感觉甚是鬼畜……

FWT类似于FFT,也是用于解决快速卷积的问题。不过,FWT解决的是位运算卷积。
比如:
其中xor可以换为or、and等各种位运算。

以xor为例。
如果只有一个元素……那么显然不变吧
如果有两个元素……
那么
构造变换,及其逆变换
那么变换后的


而当长度大于2时同样容易验证其正确性。

那么我们就可以使用T变换将卷积式转为点值表达,相乘后再用DT变换转为系数表达。
或运算与与运算同理。

or:
and:

Comments

comments powered by Disqus