FWT
本文全部大部分参考自yyb的博客
概述
FWT（快速沃尔什变换）用于解决类似B
[A_n = sum_{n = iotimes j} B_i cdot C_j
]
其中(otimes)表示二元位运算的问题。
类似FFT，我们先将数组经过FWT变换然后对应位置一一相乘，再IFWT即可。
约定
(C = A imes B Leftrightarrow C_n = A_n cdot B_n)
(C = A+B Leftrightarrow C_n = A_n+B_n)
(C = A otimes B Leftrightarrow C_n = sum_{i otimes j = n} A_i cdot B_j)
(A_x)表示数组(A)中下标最高位为(x)的位置组成的新数组。
((A, B))表示将A与B拼接组成新数组。
(F(A))表示对A数组进行FWT变换。
(IF(A))表示对A数组进行IFWT变换。
内容
[F_{|}(A) = (F_|(A_0)， F_|(A_0)+F_|(A_1)) \
F_&(A) = (F_&(A_0)+F_&(A_1), F_&(A_1)) \
F_oplus(A) = (F_oplus(A_0)+F_oplus(A_1), F_oplus(A_0)-F_oplus(A_1))
]
这里直接介绍(otimes = oplus)的情况。
性质1：
[F(A+B) = F(A)+F(B)
]
证明（数学归纳法）：
[egin{aligned}
F(A+B)
& = (F(A+B)_0+F(A+B)_1, F(A+B)_0-F(A+B)_1) \
& = (F(A_0)+F(B_0)+F(A_1)+F(B_1), F(A_0)+F(B_0)-F(A_1)-F(B_1)) \
& = (F(A_0+A_1)+F(B_0+B_1), F(A_0-A_1)+F(B_0-B_1)) \
& = ((F(A))_0 + (F(B))_0, (F(A))_1+(F(B))_1)
& = F(A)+F(B)
end{aligned}
]
性质2：
[F(Aoplus B) = F(A) imes F(B)
]
证明（数学归纳法）：
[egin{aligned}
F(Aoplus B)
& = (F(Aoplus B)_0+F(A oplus B)_1, F(A oplus B)_0 - F(A oplus B)_1) \
& = (F(A_0 oplus B_0 + A_1 oplus B_1 + A_0 oplus B_1 + A_1 oplus B_0), \
& qquad F(A_0 oplus B_0 + A_1 oplus B_0 - A_0 oplus B_1 - A_1 oplus B_0)) \
& = (F(A_0) imes F(B_0) + F(A_1) imes F(B_1) + F(A_0) imes F(B_1) + F(A_1) imes F(B_0), \
& qquad F(A_0) imes F(B_0) + F(A_1) times F(B_1) - F(A_0) imes F(B_1) - F(A_1) imes F(B_0)) \
& = (F(A_0+A_1) imes F(B_0+B_1), F(A_0-A_1) imes F(B_0-B_1)) \
& = ((F(A))_0 imes (F(B))_0, (F(A))_1 imes (F(B))_1) \
& = F(A) imes F(B)
end{aligned}
]
其余同理。
那么我们就可以愉快地计算了。
最后的问题是怎么得到原数组：逆过来就可以了。
[IF_|(A) = (IF(A_0), IF(A_1)-IF(A_0)) \
IF_&(A) = (IF(A_0)-IF(A_1), IF(A_1)) \
IF_oplus(A) = (frac{(IF(A_0)+IF(A_1)}{2}, frac{IF(A_0)-IF(A_1)}{2})
]