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