和 FWT 有点像，用在子集和超集

SOS dp

全称为 Sum over Subsets dynamic programming ，即“子集和动态规划”

引入

考虑如下问题，求：
$$
f[i] = \sum_{j \subseteq i} a_j
$$
这里的 $a_j$ 可以是任何信息，点像 FWT ，因为 $j \subseteq i$ 就是按位与等于 $j$ ，但我们其实可以 dp 搞

考虑定义 $d[x][i]$ 表示“只考虑 $x$ 二进制下前 $i$ 位的 $f[x]$ （但 $a_j$ 是所有位都考虑的）”，转移就讨论一下：

$x$ 第 $i$ 位为 $0$ ，那其实 $x$ 不变，有 $d[x][i] \gets d[x][i - 1]$
$x$ 第 $i$ 位为 $1$ ，设从 $y$ 转移，发现 $y$ 第 $i$ 位是什么都可以，所以有 $d[x][i] \gets d[x][i - 1]$ 和 $d[x][i] \gets d[x \oplus (1 << i)][i - 1]$

发现 $i$ 可以压掉，所以最后的代码是（两个循环的顺序是从大到小还是从小到大没有关系）：

1 2	for (int i = 0; i < N; ++i) for (int j = (1 << N) - 1; ~j; --j) if ((j >> i) & 1) d[j] += d[j ^ (1 << i)];

初始化为 $\forall a_j, d[a[j]] = a[j]$

上面的代码从集合角度也很好理解：就是枚举每一个元素，然后如果 $j$ 有这个元素，$j \oplus (1 << i)$ 就是它的一个子集

也可以从高维前缀和的角度理解，类似集合

一些定义

先给出超集和子集的定义：

对于集合 $A \subset B$ ，我们称 $A$ 为 $B$ 的子集， $B$ 为 $A$ 的超集

而 SOS dp 就是用来解决有关它们的问题的

例题

Jzzhu and Numbers

题意

给定 $n \le 10^6$ 个非负整数 $a_i \le 10^6$ ，定义一个集合的权值为其中元素按位与的值，求权值为 $0$ 的子集个数

思路

考虑与在集合意义下的定义， $a \& b = a$ 意味着 $b$ 是 $a$ 的子集， $a$ 是 $b$ 的超集，考虑定义 $d[x]$ 表示“ $x$ 的原数列中超集个数”，显然转移的时候是 if (!(j >> i) & 1) d[j] += d[j ^ (1 << i)] ，最后 $2^{d[x]} - 1$ 就是“权值为 $x$ 的超集（包括 $x$ ）的集合个数”（两个集合是不一样的），我们要想办法去掉超集（不包括 $x$ ）的答案，就反着（加变减）做一次超集的 SOS 即可

代码

要注意的地方就是 NN 的大小是 $\log a$

#include <bits/stdc++.h>
const int N = 1e6 + 100, NN = 21, P = 1e9 + 7;
int n, a[N], d[(1 << NN) + 100], pw2[N];
void adj(int &x){ x += (x >> 31) & P; }
int main()
{
	scanf("%d", &n);
	pw2[0] = 1;
	for (int i = 1; i <= n; ++i) adj(pw2[i] = pw2[i - 1] + pw2[i - 1] - P);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), adj(d[a[i]] += 1 - P);
	for (int i = 0; i < NN; ++i)
		for (int j = (1 << NN) - 1; ~j; --j) if (!((j >> i) & 1)) adj(d[j] += d[j ^ (1 << i)] - P);
	for (int i = (1 << NN) - 1; ~i; --i) adj(d[i] = pw2[d[i]] - 1);
	for (int i = 0; i < NN; ++i)
		for (int j = (1 << NN) - 1; ~j; --j) if (!((j >> i) & 1)) adj(d[j] -= d[j ^ (1 << i)]);
	printf("%d\n", d[0]);
	return 0;
}

例题二

Prefix XORs

题意

给定长度为 $n \le 10^6$ 个非负整数序列 $a_i \le 10^6$ ，要对其进行 $m \le 10^6$ 次前缀异或和，对于每一次，输出 $a_n$ 的值

思路

考虑每一个数被算了几次，写出如下矩阵（设 $n = 5$ ）：
$$
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
5 & 4 & 3 & 2 & 1 \\
15 & 10 & 6 & 3 & 1 \\
35 & 20 & 10 & 4 & 1 \\
70 & 35 & 15 & 5 & 1
\end{bmatrix}
$$
发现是杨辉三角（斜着的），可得第 $k$ 次前缀和，第 $i$ 个位置的计算次数就是 $\binom{n - i + k - 1}{k - 1}$ ，这个东西也就等于 $\binom{n - i + k - 1}{n - i}$

当然不能直接算，在异或意义下我们只关心其奇偶性，即 $\binom{n - i + k - 1}{n - i} \mod 2$ ，考虑 Lucass 定理，我们只关心上下两个数二进制下每一个组合数的积，发现 $\binom{1}{0} = 1, \binom{1}{1} = 1, \binom{0}{0} = 1, \binom{0}{1} = 0$ ，显然只要有一个 $0$ 积就是 $0$ 了，所以要 $\binom{n - i + k - 1}{n - i} \equiv 1 \pmod 2$ ，二进制下每一位组合数都要是 $1$ ，则有 $(n - i) \subseteq (n - i + k - 1)$ ，即 $(n - i) \cap (k - 1) = \varnothing$ ，又即 $\overline{(n - i)} \subseteq (k - 1)$

考虑对每个 $\overline{(n - i)}$ 求出其超集的异或值即可

代码

#include <bits/stdc++.h>
const int N = 1e6 + 100, NN = 21;
int n, m, a[N], d[(1 << NN) + 100];
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		d[(1 << NN) - 1 - n + i] = a[i];
	}
	for (int i = 0; i < NN; ++i)
		for (int j = (1 << NN) - 1; ~j; --j) if (!((j >> i) & 1)) d[j] ^= d[j ^ (1 << i)];
	for (int i = 1; i <= m; ++i) printf("%d ", d[i - 1]);
	return 0;
}