我们想要知道的是：对于某个集合$S$, $\sum\limits_{R\subseteq S}{x(R)}$ (子集dp) 或者 $\sum\limits_{U\supseteq R\supseteq S}{x(R)}$ (超集dp)，$x$表示集合的某个性质

这里的加法也可以换成 min,max

求加法的相应dp叫做 SOS(sum on supersets/subsets) dp，求min,max的相应dp叫做 MOS(min/max on supersets/subsets) dp

这里以 SOS dp 为例子，我们通过二进制表示集合，这样就可以把每个集合映射到一个整数了

令 $f[msk][p]$ 为msk改变后p位能形成的msk子集/超集的结果

子集dp: $$ f[msk][p]=\begin{cases} f[msk][p-1]+f[msk \oplus 2^{p-1}][p-1] & 若msk的第p位是1\\ f[msk][p-1] & 若msk的第p位是0 \end{cases} $$

超集dp: $$ f[msk][p]=\begin{cases} f[msk][p-1]+f[msk \oplus 2^{p-1}][p-1] & 若msk的第p位是0\\ f[msk][p-1] & 若msk的第p位是1 \end{cases} $$

可以看到，子集dp和超集dp的转移方程基本是一样的，除了条件要反一下

外层循环枚举$p$，内层循环枚举$msk$，$p$这一维可以滚动数组优化，且两层循环的枚举顺序可以任意

结果就是 $f[S][nElements]$