高维前缀和 笔记

你知道学完一个东西不写笔记会有什么后果吗？——直接失忆。

一、高维前缀和

考虑求二维前缀和，除了传统的容斥方法，还可以这样：

// 考虑第一维
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) // 每个点加上这一维上个点的和
        a[i][j] += a[i - 1][j];
// 考虑第二维
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) // 每个点加上这一维上个点的和
        a[i][j] += a[i][j - 1];

考虑这份代码是在干什么（如注释所示）。

因此，求高维前缀和可以：

• 考虑每一个维度。
• 所有点加上这个维度上个点的信息。

二、SOS DP

1. 子集

对于每一个状态 $s\in [0,2^n)$，我都希望求出他的所有子集的相关信息。事实上可以把 $s$ 看成一个 $n$ 维前缀和，每一维的边长只有 $2$，那么他的所有子集，就是相当于求他的前缀和。时间复杂度 $O(n\times 2^n)$。

2. 超集

从前缀和变成了后缀和。

三、刷题总结

这个东西还是要看题目才能理解。

1. AT_arc100_c [ARC100E] Or Plus Max

显然可以将 $i|j\le K$ 转换为 $i|j=K$，再对答案求前缀和。$i|j=K\Rightarrow i\subset K,j\subset K$。要 $A_i+A_j$ 最大，就是要下标是 $K$ 的子集的数中，找到最大的两个数。设 $f_K$ 表示这个东西，高维前缀和即可。

2. CF165E Compatible Numbers

$x\mathrm{\&}y=0\Rightarrow x\subset \bar{y}$，设 $f_x$ 表示数 $x$ 的子集中一个存在的数，高维前缀和即可。查询 $x$ 就查询 $f_{\bar{x}}$。

3. CF449D Jzzhu and Numbers

$a_{i_1}\mathrm{\&}{a}_{i_2}\mathrm{\&}\dots \mathrm{\&}{a}_{i_k}=x\Rightarrow \mathrm{\forall }p,x\subset a_{i_p}$。设 $f_x$ 表示选择若干个数按位与得到 $x$ 的方案数。看似只要求 $x$ 的高维后缀和就好了，但实际上可能选出来的数按位与之后还是 $x$ 的超集，所以 $f_x$ 实际是选择若干个数按位与至少是 $x$，那么容斥一下就好了。由于最后只要求 $f_0$，对 $x$ 中 $1$ 的个数进行容斥即可。即设 $g_i$ 表示按位与出来至少有 $i$ 个 $1$ 的方案数。

4. P6442 [COCI 2011/2012 #6] KOŠARE

看数据范围，玩具种类很小，直接对每个箱子有的玩具状压，选出来之后要包含所有的玩具，那么就是选择的箱子按位或后全部是 $1$。设 $f_x$ 表示选择若干个数按位或得到 $x$ 的方案数，高维前缀和，和上一题同理容斥。

5. CF1208F Bits And Pieces

考虑从高到低贪心确定答案每一位能否为 $1$，假设当前可能的答案是 $x$，那么由于是或，可以让 $a_i$ 贡献其中的 $y\subset x$，让 $a_j\mathrm{\&}{a}_k$ 贡献其中的 $z\subset x$（$y|z=x$）。设 $f_x$ 表示只选择一个数 $a_i$ 满足 $x\subset a_i$，最小的下标 $i$。设 $g_x$ 表示选择两个数 $a_j,a_k$ 满足 $x\subset a_j\mathrm{\&}{a}_k\Rightarrow x\subset a_j\wedge x\subset a_k$，下标 $j,k$ 的最大值。做一次高维后缀和。$O(\log V)$ 枚举每一位，$O(2^{\log V}=V)$ 分配 $y,z$。总时间复杂度 $O(n+V\log V)$。