[BZOJ 2839] 集合计数

发布时间 2023-06-14 20:10:06作者: Joker__King

首先求一个集合的个数可由 \(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\) 种交集。