OI wiki 上给出的公式:
Ai=∑C1Aj−∑C2Ak
其中 C1 为 popcount(i∣j) 模 2 为0,C2 为 1。
然后给出的 Merge 是这样的:
fwt(a)=merge(fwt(a1)−fwt(a0),fwt(a1)+fwt(a0))
但是按照增量构造的方法,添加第 i 位后,a0 里的第 i 位都是 0,a0 里的第 i 位都是 1。自己推出来是:
merge(fwt(a0)−fwt(a1),−fwt(a0)−fwt(a1))。
我的想法是:添加第 i 位后,原来的 a0 放到左边时,下标和 a0 里的下标第 i 位都是 0 所以没有新增 1,所以累加上去。然后原来的 a1 下标的第 i 位都变成了 1,所以不管放到左边还是右边都应该是减去;然后因为右边的每个下标的第 i 位都是 1,a0 放到右边也应该是减去的形式。
不知道问题出在了哪里,还是说我对分治增量构的理解有误qwq