[BZOJ 2839] 集合计数

首先求一个集合的个数可由 \(2 \cdot 2 \cdot 2 \cdot 2...\) 得到，其中每个二表示选或者不选本个元素。即一个有 \(n\) 个元素的集合存在 \(2^n\) 个子集

然后同理可得从 \(2^n\) 个子集中选交集的方案数为 \(2 \cdot 2 \cdot 2 \cdot 2...\) (共包含 \(2^n\) 个 \(2\)) 所以总数为 \(2^{2^n}\) 个选方式，但因为原子集存在空集，所以存在只选空集和都不选的重复情况(这里的重复指在后面选择时的重复，在只选集合 \(k\) 其他都不选时与选集合\(k\) 和∅时它们的集合并起来时一样的，都为 \(k\)。至于为什么不把选空集的交集都排掉，是因为若除了空集外的其他集合与空集的交集固然为空集，但除了空集外的其他集合与空集的并集不同于只选空集，所以不一样，不用排掉)，所以要减一为 \(2^{2^n}-1\) 种交集。