快速沃尔什变换

落后于时代。。正式退役之后一天学会FWT

好像资料不是很多。。大概是我没好好找= =

虽然还不是那么理解 赶快来现学现卖一发

仿照FFT教程来?

然后发现我并不知道这类问题应该叫什么

于是不分节好了

问题:求\(C=A \bigotimes B\),其中\(C_i=\sum_{j\otimes k=i}A_j B_k\)。

其中\(\otimes\)为一二元逻辑位运算。

这个卷积可以用FWT优化到\(nlogn\)。

思想和FFT类似:构造一个变换\(tf\)使得\(tf(A)_i\times tf(B)_i=tf(A\otimes B)_i\)和它的逆变换\(ft\)。

变换同样进行分治,每次考虑一位。设多项式\(A\)中当前位为\(0\)的部分为\(A_0\),当前位为\(1\)的部分为\(A_1\),表示为\(A=(A_0,A_1)\)。

对于与运算:

\(tf(A)=(tf(A_0)+tf(A_1),tf(A_1))\)

\(ft(A)=(ft(A_0)-ft(A_1),ft(A_1))\)

对于或运算:

\(tf(A)=(tf(A_0),tf(A_1)+tf(A_0))\)

\(ft(A)=(ft(A_0),ft(A_1)-ft(A_0))\)

对于异或运算:

\(tf(A)=(tf(A_0)+tf(A_1),tf(A_0)-tf(A_1))\)

\(ft(A)=(\frac{ft(A_0)+ft(A_1)}{2},\frac{ft(A_0)-ft(A_1)}{2})\)

对于其他位运算,可以用以上三种运算和非组合得到。

对与操作变换的理解:\(tf(A)_i=\sum_{i\&j=i}A_j\),类似于前缀和。显然可以直接进行乘法。

对或操作变换的理解:和与操作类似。

对异或操作变换的理解:\(tf(A)_i=\sum_{j}(-1)^{c(i\&j)}A_j\),其中\(c\)表示二进制所含\(1\)的个数。显然\((-1)^{c(i\&j)}(-1)^{c(i\&k)}=(-1)^{c(i\&(jˆk))}\)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz