快速沃尔什变换(FWT)讲解 解决集合卷积的方法
能看到这篇博客的人,一定知道FWT是干什么的。(什么?你不知道?)
没事,这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了,那么恭喜你。如果你跟我一样看不懂,那么请继续往下看。
这里的A和B都是什么呢?其实它们是一个多维的向量(如果你不知道向量是什么,就把它当成数组),下标从0开始。
其中,$ A = <a_{0},a_{1},...,a_{2^{k}-1}> $,$ B = <b_{0},b_{1},...,b_{2^{k}-1}> $,$ C = A\otimes B $
这里我们定义$$ A\pm B = < a_{0}\pm b_{0},...