容斥

这是一个用交集求并集的方法。

对于 $n$ 个条件，满足其中至少一个的并集，为满足奇数个的交集 $-$ 满足偶数个的交集。

证明就是 ${n \choose 1} - {n \choose 2} + {n \choose 3} - \cdots \pm {n \choose n} = 1$，这样每个状态正好取一次。