萌新求助 FWT 同或
  • 板块学术版
  • 楼主Cry_For_theMoon
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/10/1 09:07
  • 上次更新2023/11/4 05:16:22
查看原帖
萌新求助 FWT 同或
340632
Cry_For_theMoon楼主2021/10/1 09:07

OI wiki 上给出的公式:

Ai=C1AjC2AkA_i=\sum_{C1}A_j-\sum_{C2}A_k

其中 C1C1popcount(ij)popcount(i|j)22 为0,C2C2 为 1。

然后给出的 Merge 是这样的:

fwt(a)=merge(fwt(a1)fwt(a0),fwt(a1)+fwt(a0))fwt(a)=merge(fwt(a_1)-fwt(a_0),fwt(a_1)+fwt(a_0))

但是按照增量构造的方法,添加第 ii 位后,a0a_0 里的第 ii 位都是 00a0a_0 里的第 ii 位都是 11。自己推出来是:

merge(fwt(a0)fwt(a1),fwt(a0)fwt(a1))merge(fwt(a_0)-fwt(a_1),-fwt(a_0)-fwt(a_1))

我的想法是:添加第 ii 位后,原来的 a0a_0 放到左边时,下标和 a0a_0 里的下标第 ii 位都是 00 所以没有新增 11,所以累加上去。然后原来的 a1a_1 下标的第 ii 位都变成了 11,所以不管放到左边还是右边都应该是减去;然后因为右边的每个下标的第 ii 位都是 11a0a_0 放到右边也应该是减去的形式。

不知道问题出在了哪里,还是说我对分治增量构的理解有误qwq

2021/10/1 09:07
加载中...