容斥原理

总结一下容斥。主要是一些题目。

Min-Max 容斥

设 $S = \{1, 2, 3, \ldots, n\}$。对于长度为 $n$ 的序列 $x_i$，有：

$$\max_{i \in S} x_i = \sum_{T \subseteq S} (-1)^{|T| - 1} \min_{j \in T} x_j\\ \min_{i \in S} x_i = \sum_{T \subseteq S} (-1)^{|T| - 1} \max_{j \in T} x_j$$

【证明】 还没写。

杂题

UVA11806 Cheerleaders

题意

有一个 $n \times m$ 的网格图，需要放 $k$ 个人，满足以下条件：

• 网格图的四个边上都至少有一个人（四个角的人可以算作同时在两个边上）。
• 每个格子上不能有两个人。
• 每个人必须都有位置。

求方案数。

考虑容斥。将四个边上都“至少有一个人”，反向转化为四个边上至少有一条边没人。

然后容斥掉“至少”的限制。设 $A_i$ 表示第 $i$ 条边没人的方案集合，则四条边上至少有一条边没人的方案数为：

$$\sum |A_i| - \sum|A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \sum|A_i \cap A_j \cap A_k \cap A_w|$$

某一行没人相当于删掉一行，某一列没人相当于删掉一列。剩下随便取即可。