0 引

为什么没在标题里写 SOS DP ？因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经，所以写全称让他看着正经一些。

个人感觉这个东西更像是一个套路而不是 DP 类型。

1 什么是 SOS DP

Sum over Subsets DP，即求子集和的 DP。更具体的说，用于在 $O(k \cdot 2^k)$ 的时间求出以下式子：

$$ f_{mask} = \sum_{i \subseteq mask} a_i $$

题目链接：https://codeforces.com/contest/383/problem/E

1 题目大意

给定 $n$ 个长度为 $3$，字符集为 a-x 的字符串。

对于 $s, s \subseteq [ \texttt{a}, \texttt{x} ]$，有 $f(s)$ 表示有多少个给定字符串和 $s$ 交集非空。

输出 $\sum^{\oplus}_s f(s) * f(s)$

2 思路

注意到基本上是 SOS DP 的模版，除一个问题 -- 对于一个字符串可能会被统计多次。

简单容斥即可。

题目链接：https://codeforces.com/contest/165/problem/E

1 题目大意

给定一个长度为 $n$ 的序列 $a$。

对于每一个 $a_i$，询问是否存在 $a_j$ 使得 $a_i & a_j = 0$，如果有输出 $a_j$（如果有多个，输出任意一个），否则输出 $-1$。

$1 \leq n \leq 10^6, 1 \leq a_i \leq 4\cdot 10^6$。

2 思路

注意到 $a_i & a_j = 0$，其实就是询问是否有数字满足其是 $a_i$ 的补集的子集。

SOS DP 求出每个集合是否有数字是其子集即可。

题目链接：https://codeforces.com/contest/1208/problem/F

1 题目大意

给定一个长度为 $n$ 的序列 $a$

求最大 $a_i|(a_j&a_k)$ 满足 $i < j < k$

$3 \leq n \leq 10^6, 0 \leq a_i \leq 2 \cdot 10^6$

2 思路

先考虑 $a_j&a_k$，显然可以通过 SOS DP 来求出对于任意 $s$，其最靠后 $j$ 的能够有 $k$ 使得 $s \subseteq a_j&a_k$ 的位置。

然后考虑贪心来最大化按位或，从高位往低位处理，如果能够有一位新为 $1$，则有限选择位数高的。

原题链接：https://codeforces.com/contest/1549/problem/E

题目大意

给定 $n$，$q$ 次询问。

每次询问给定一个 $x$，求 $\sum_{i=0}^n \binom{3i}{x}$

思路

考虑定义 $f_{i,j}$ 表示 $\sum_{k=0}^{n-1} \binom{3k + j}{i}$，令 $0 \leq j < m$

注意到

1. $\sum_{j=0}^{m-1} f_{i,j} = \sum_{j=0}^{3n - 1} \binom{j}{i} = \binom{3n}{i + 1}$
2. $f_{i,j} = f_{ i - 1, j - 1 } + f_{i, j - 1 }$

发现可以解出 $f_{i,0}$

$O(n)$ 递推即可。