前言
本文用集合的符号表示二进制数。具体地，定义全集 (u) 是 (2^n-1)，某个二进制数 (x) 第 (t) 位是 1 可以理解为为 (x) 中有 (t) 号元素，否则没有。定义 (|x|) 代表的不是二进制数的绝对值，而是 1 的个数。(x subseteq y) 当且仅当 (x& y = x) 。其它符号类似。
一类问题
对于一个数列 (b) ，定义它的一种变换是 (B_i = bigopluslimits_{j subseteq i}{b_j}) 现在给出 ({B_i}) ，求 ({b_i}) 。
一个恒等式
[bigopluslimits_{tsubseteq ysubseteq x}{((u-x)oplus y)} = begin{cases}
u, &t=x\
0, &|t| < |x|-1\
toplus x, &|t| = |x|-1
end{cases}
]
解决
基于上面的恒等式设计一种反演（按位与对异或有分配律）：
[begin{align*}
b'_i &= bigopluslimits_{j subseteq i}{((u - i) oplus j)&B_j} & &(ast)\
&= bigopluslimits_{j subseteq i}{left[((u - i) oplus j)&bigopluslimits_{tsubseteq j}{b_t}right]}\
&= bigopluslimits_{t subseteq i}{left[b_t&bigopluslimits_{tsubseteq jsubseteq i}{((u - i) oplus j)}right]}\
&= b_ioplusleft(bigopluslimits_{k=0}^{|u|}{2^k&i&b_{i-2^k}}right)
end{align*}
]
其中的 ((ast)) 式可以通过对 ({B_i}, {i& B_i}) 两个数列进行高维前缀和预处理来做到 (Theta(nlog n)) 求得。
下面的问题是怎么把 (b') 后面拖着的尾巴去掉，把它变回 (b) 。注意到 (i-2^k < i) ，所以按照从小到大的顺序还原 (b) ，当处理到 (b_i) 时直接枚举 (i) 的所有二进制位进行一个异或，就把后面消掉了，时间复杂度依然是 (Theta(nlog n)) 。
应用
感觉没用。谁哪天用上了记得v我50。
程序员灯塔
转载请注明原文链接：一种关于子集异或和的冷门反演
转载请注明原文链接：一种关于子集异或和的冷门反演