今天模拟赛碰上 FWT 一直没学直接歇了,于是决定补 FWT,然后搜到了 yyb 大佬的博客,但看着看着似乎感觉写得有些问题,有没有大佬帮忙看下是不是真的出问题了还是我理解错了。
这篇博客
关于异或运算的证明的第二个等号到第三个等号,即:
=(FWT[(A0⊕B0)+(A1⊕B1)+(A0⊕B1)+(A1⊕B0)],FWT[(A0⊕B0)+(A1⊕B1)−(A0⊕B1)−(A1⊕B0)])
=((FWT[A0]+FWT[B1])×(FWT[A0]+FWT[B1]),(FWT[A0]−FWT[B1])×(FWT[B0]−FWTB1))
这个转化疑似用到了本身要证明的 FWT[A⊕B]=FWT[A]×FWT[B],感觉这里似乎是循环论证了?求大佬帮忙看下。