真·浅谈高维前缀和/sosdp |

夜空是否全然知晓？

高维前缀和/sosdp

计算高维前缀和可以不用容斥，而是对每一维分别做前缀和，复杂度为 $O(kn)$ ，其中 $k$ 是维度。

对于子集求和问题，相当于二进制下的 $1$ 可以选 $0$ 或 $1$ ， $0$ 只能选 $0$ ，类似于一个高维的前缀和问题。

那么就可以在 $O(n 2^n)$ 的复杂度之内求出类似于子集和的问题。

$i \in k,j \in k$ 是 $i | j = k$ 的必要条件，是 $i|j<=k$ 的充分条件。

先算出 $=k$ 的答案，在求个前缀最小值就算出了 $\leq k$ 的答案，然后也满足了充要。

然后就是求子集最大值和次大值，高维前缀和解决。

考虑枚举一个 $i$ ，然后 $d_i|(d_j \& d_k)=d_i+(d_i \& d_j \& d_k)$ 。

要使得 $d_i \& d_j \& d_k$ 更大，从高位到低位贪心的看能不能是 $1$ 。

假设当前选择的为 $s$ ，首先 $d_i \in s$ ，然后存在 $j,k$ 使得 $i < j < k$ 并且 $d_j \in s,d_k \in s$ 。

相当于求一个超集的最大值和次大值，这种类似子集和的问题可以用高维前缀和解决。

设选择的集合为 $s$ ， $f_s$ 为 $\in s$ 的个数，那么集合 $\in s$ 的个数为 $2^{f_s}-1$ 。

$f_s$ 可以用高维前缀和算，然后按照 $1$ 的个数容斥就行了。

也可以再跑一遍差分。

和上一道类似，不过不是跑子集是跑超集。

然后跑容斥或者差分。