容斥

BrotherCall · 2025-04-10 21:34:37 · 个人记录

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

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

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