前言(胡说。 可以跳过) :
其实去年清华集训之后，我就想写这篇文章了……但是写了一段时间，我发现自己有点不懂语言……所以受限于语文水平，一直没有写。 因为前几天和人面对面说了话，所以我觉得大概BB会懂一点……
picks的博客上写着fwt怎么做，但他没有写为什么那个是正确的
去年清华集训后的一天，ljss和我一起刷了清华集训问题。 然后他突然向我提出了问题。 给定数组a，以确定b[i]=对于所有j满足j|i==i，sigma a[j]的数组b。
YY过了一会儿，我在YY做了分期统治的做法。 然后ljss告诉我这是清华集训D1T2的简化版。 然后又告诉我这个问题是FWT。 过了一会儿，我觉得YY的做法是这个尼玛是不是FWT的正变换
然后，和ljss一起进行了长时间的盲目的YY，终于YY从FWT出来了到底是什么jb
如果发现写了问题，请马上评论-_-
FWT能做什么： FWT对于两个数组a和b，可以求出他们的位运算卷积c，使得c[k]=对于所有I和j，I位运算j等于k sigma a[i]*b[j]
首先谈卷积和和或卷积，最后谈异或卷积
很简单的问题。 前言：想想前言中提到的问题
给出序列a，求出序列b，使得b[i]=对所有j满足j|i==i、sigma a[j]
我们考虑逐位分割统治，首先将数组的长度补充为0到2的乘方
可以将长度为2^l的原始数组按最高位0和最高位1分为两部分，而不考虑最高位
如果递归地处理这两个部分，则假设得到了当前对最高位为0所有下标求出的b数组b0和对最高位为1的所有下标求出的b数组b1，它们的长度都为2^(l-1 )
那么，现在考虑最高位的影响。 将计算最高有效位影响后的长度为2^l的b数组左右分开，标记为bn0和bn1，即最高有效位为0的部分和最高有效位为1的部分，他们的长度也为2^(l-1 )
那么，对于任意的I和j，如果j|i不等于I，则向I和j添加最高有效位后的j|i也一定不等于I，因此bn0[i]和bn1[i]只与b0[i]和b1[i]有关
另外一方面，如果j|i等于I，则I加上最高位ih，j加上最高位的jh，则最高位的j|i是否等于I，只与jh|ih是否等于ih有关
那么显然可以得到bn0[i]=b0[i]，bn1[i]=b0[i] b1[i]
我想很明显YY也可以
b[i]=如果要求对所有j满足ji==i，sigma a[j]，则bn0[0]=b0[i] b1[i]，bn1[i]=b1[i]
这样，可以在n log n的时间内求出b排列
可以看到这实际上是或卷积的正变换
以后，求出b数组也称为正变换
或者卷积，以及卷积的原理。 或卷积和卷积事实上基于以下原理：
ik==k且jk==k与(ij ) k==k等价
i|k==k且j|k==k等价于(i|j )|k==k
那么，在要求数组a和数组b的卷积或卷积的情况下，只要求出a的正变换a '和b的正变换b '，求出另一个c'[i]=a'[i]*b'[i]，c '就进行了a和b的卷积为正的变换
我们现在只需要给你一个正变换后的结果，思考如何逆变换求原数组
逆变换：逆变换的过程实际上是解密的过程，正变换相当于加密
还是从左右考虑。 正变换时，我们设定bn0[i]=b0[i]，bn1[i]=b0[i] b1[i]。 那么，如果现在知道的是bn0和bn1，那么很容易理解b0[i]=bn0[i]，B1[I]=
与运算的逆变换相同
然后左右递归就可以了
你可能会怀疑。 进行正变换时，我们首先递归地考虑左右任意一位，而进行逆变换时，需要先考虑任意一位再递归地考虑两侧吗
实际上，由于每个位都是等效的，所以可以像反向变换一样递归地考虑这个位，而与顺序无关
“异或”(卷积)“异或”和其他的又不一样……所以我们YY很久以前就理解了“异或”卷积是什么样的鬼畜
卷积基于以下原理：
定义I和j之间的偶奇性为ij中1位的偶奇性，偶数的话偶奇性为0，奇数的话偶奇性为1
那么，I和k的奇偶异或j和k的奇偶校验等于i^j和k的奇偶校验
很明显YY就行了
那么，正变换序列a后的序列b的含义是b[I]=(-(sigma j满足I和j的奇偶校验==0 a[j] )-) sigmaj满足I和j的奇偶校验==1 a[j] )
在中，如果要求将c卷积到a和b的异或中，另一个a正变换为a '，b正变换为b '，再正变换为c'[i]=a'[i]*b'[i]，则c '正好是c正变换后的结果
很明显，如果觉得不明显的话，稍微YY一下就知道了
那么，想想如何进行正变换和逆变换比较好吧。 还是说，按位进行划分也不错吧
在正变换的情况下，设为bn0[i]=b0[i] b1[i]，bn1[i]=b0[i]-b1[i]
在逆变换的情况下，B0[I]=(bn0[I]bn1[I] )/2，B1[I]=) bn0[I]-bn1[I] )/2
正确是显而易见的
完结花_M