2023-05-12-集合DP

我们想要知道的是：对于某个集合, (子集dp) 或者 (超集dp)，表示集合的某个性质

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

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

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

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

子集dp:

若 的 第 位 是 若 的 第 位 是

超集dp:

若 的 第 位 是 若 的 第 位 是

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

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

结果就是