记一类异或问题:嗯背fwt在干什么

据我所知,FWT 在 CTT 之前都不考,我的建议是:别学

引言

对于 OI 界的一些较为简单的异或问题,涉及到的算法其实不多:集合幂级数、线性基、0-1 trie,剩下的就是对着异或的性质嗯遍做法,比如位运算可以按位拆,异或做两次等于没做(异或函数的反函数就是他自己)之类的。在这其中,又有这么一类问题,求一个序列有多少子集异或和为 X 。这个问题看起来十分 simple ,套一个线性基就做完了,但是大的要来了:如果这个问题稍加修改,每个子集如果异或和为 X,会对答案产生一个贡献,贡献是一个关于子集大小的函数,这个时候我们发现我们就不能直接套用老方法了,因为线性基并不能求出选了 k 个数并且异或和为 X 的方案数,结果尴尬了。

P1:「Uoj310」【UNR #2】黎明前的巧克力

对于这个问题,首先我们要做出一个转化,既然我们想要找到两个不交的子集并且异或和相同,那我们不妨考虑先找到这两个子集的并,再考虑这两个子集的分配。幸运的,我们发现两个子集的并有一个很好的性质:这个子集的异或和为 0,并且两个子集在这个并内的分配方案么有任何限制,我们可以选出任何一个子集作为 S ,剩下的部分作为 T,都能满足题目中给出的条件。那么显然的,一个异或和为 0 的子集,他一共有 $2^{|S|}$ 种方案贡献给答案(如果我们暂且认为两个空集是合法的)。这样,这个问题就变成了我们引言中描述的形式了。

这时显然不能线性基,也不能 0-1 trie,那么我们不妨考虑是否能用集合幂级数解决这个问题,也就是 fwt。

考虑最暴力的做法是什么,我们借鉴一下背包的做法,每次考虑一个物品选或不选,那么在这个问题中我们也可以这么做,设 DP 数组 f ,对于一个数 $a_i$ 有转移:

显然对于第二维的转移,可以用 fwt 进行优化,但是看起来并没有什么优化的必要,因为复杂度依然十分危险,为 $O(nm2^m)$ 。

但是考虑到每个转移的幂级数都是形如 $1+2x^{a_i}$ 的形式,我们不妨考虑他有没有特殊的性质。

中所周知,若我们对一个长度为 $2^m$ 的数组 A 作一次 FWT 得到的数组 B,那么有 $B_i = \sum_{j}A_j (-1)^{popcount(i\&j)}$ ,而 FWT 的逆变换$IFWT = FWT \cdot 2^{-m}$ ,也就是做一次 FWT 后每个数乘上 $2^{-m}$ 。

这时我们发现,因为每个转移的幂级数形式特殊,使得这个 A 数组只有两处有值,并且 $A_0$ 是其中一处,也就是说 B 的取值也只会有两种:-1 或 3 。那么考虑我们做自己卷积的过程:对于每个 $a_i$ ,我们构造对应的系数数组 $A^i$,然后对其作一次 FWT 得到结果数组 $B^i$,最后我们把所有 $B^i$ 点乘起来得到最后的答变换案数组 $B^{ans}$,做 FWT 逆变换即可。显然由于上面的结论,我们知道了 $B^{ans}_i = 3^{k_i}(-1)^{n-{k_i}}$ 。那么我们只需要知道最后的 $k$ 数组,我们就可以还原出 $B^{ans}$ 。

现在考虑如何去求 $k$ ,我们不妨直接对原序列 $\{a\}$ 看做一个幂级数 $\sum x^{a_i}$,直接做一遍 FWT 得到结果数组为 $B^0$,考虑会得到怎样的结果,对于一个数 $a_i$ 和一个位置 pos ,如果 $B^i_{pos} = -1$ 那么他对 $B^0_{pos}$ 的贡献就是 -1,否则他对 $B^0_{pos}$ 的贡献就是 1 。也就是说,最后的 $B^0_i = k_i - (n-k_i),k_i=\frac{B^0_i+n}2$ 。至此我们就成功求得了数组 $k$ ,也可以成功还原出 $B^{ans}$ 数组,只需要再做一次 IFWT 就可以得到真正的答案数组了。由于这题我们最后只需要求异或和为 0 的方案数,也就是 $A^{ans}_0$ 的值,所以我们甚至不用真的做 IFWT 还原 $B^{ans}$ ,只需要再次使用上面提到的性质考虑 $B^{ans}$ 各处对 $A^{ans}_0$ 的贡献即可。

最后复杂度 $O(n+m2^m)$ 。

P2:ZR1943 异或数数

上个题还比较温和,我们可以 $2^k$ 拆分成 $2^{k-1}\cdot 2$ 来写出转移,但是这个题就很直球了,直接对于每个 k 求出子集大小为 k 的方案数,怎么办呢。

这个时候我们直接黑化,为什么集合幂级数的系数就不能是幂级数了?进一步的,引进二元生成函数 $f(x,y) = \sum{a_{i,j} x^i y^j}$ ,其中 y 的指数表示当前的异或和,x 的指数表示当前选了几个数,然后卷积就是 y 这一维做异或卷积,x 这一维作一般卷积即可,说人话的话,就是我们把原本的 A 数组,其中的元素从数字扩展到了多项式。

那么考虑一次转移的幂级数长啥样,显然就是 $1x^0y^0 + x^1y^{a_i}$ ,那么显然 $B^i$ 里也只有两种元素 : $1-x$ 和 $1+x$ 。后面的都一样,我们依然求出 k 数组,还原出 $B^{ans}$, 但是这个时候我们就不能直接对 $B^{ans}$ 做 IFWT 了,因为多项式的加减法复杂度实在承受不住,考虑我们的第二个方法,$B^{ans}$ 各处对 $A^{ans}$ 的贡献,那么最后的答案就是 $\sum c_i (1-x)^i(1+x)^{k-i}$ ,这个式子可以分治去求,至此我们就完成了对答案的计算。

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信