好久没有用过博客了
以前做fwt,fft的题都是套板子 这里补一下原理
FWT:
与运算：
结论：$FWT(A)_i=sum_{i&j=i}^{}A_j$
$FWT(C)_i=FWT(A)_i*FWT(B)_i=(sum_{i&j=i}^{}A_j)(sum_{i&k=i}^{}B_k)=sum_{i&j&k=i}^{}A_jB_k$
求解这个式子我们考虑分治
将序列补全为长度为$2^n$,另前半部分为$A_0$(即首位为0),后半部分为$A_1$(即首位为1)
容易得到
$FWT(A)=(FWT(A_0)+FWT(A_1),FWT(A_1))$
这样就可以$nlogn$得到
反演也很容易得到
$IFWT(A)=(IFWT(A_0)-IFWT(A_1),IFWT(A_1))$
或运算:
结论：$FWT(A)_i=sum_{i|j=i}^{}A_j$
$FWT(C)_i=FWT(A)_i*FWT(B)_i=(sum_{i|j=i}^{}A_j)(sum_{i|k=i}^{}B_k)=sum_{i|j|k=i}^{}A_jB_k$
$FWT(A)=(FWT(A_0),FWT(A_1)+FWT(A_0))$
$IFWT(A)=(FWT(A_0),FWT(A_1)-FWT(A_0))$
异或运算:
这个运算和前两种略有不同
设p(x)表示x这个数二进制意义下的1的个数，
结论：$FWT(A)_i=sum_{(i&j)\%2=0}^{}A_j-sum_{(i&j)\%2=1}^{}A_j$
证件见https://blog.csdn.net/huangzihaoal/article/details/112443162
$FWT(A)=(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))$
$IFWT(A)=((FWT(A_1)+FWT(A_0))/2,(FWT(A_1)-FWT(A_0))/2)$