• 欢迎光临~

一种关于子集异或和的冷门反演

开发技术 开发技术 2022-12-09 次浏览

前言

本文用集合的符号表示二进制数。具体地,定义全集 (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。

程序员灯塔
转载请注明原文链接:一种关于子集异或和的冷门反演
喜欢 (0)