容斥定理——用于求若干集合并集的实际大小
\(Q\)：一共有 \(n\) 个集合（\(S_{1},S_{2},...,S_{n}\)），每个集合中的元素均已知，用计算式表示它们的并集大小
辅助理解：相当于枚举 \(\{S_{1},S_{2},...,S_{n}\}\) 的所有子集并将子集内的 \(S_{i}\) 取交集，子集大小为奇数取正，偶数取负，最后作和，即为并集大小。
例题:
HAOI2008 硬币购物
最暴力的做法显然是将每个硬币单独看待，然后01背包求方案数（或者直接看作是分组背包），复杂度 \(O(4ndS)\)。
此题特殊的地方在于硬币种类数只有 \(4\) 种，本质上是求满足下式的 \(\{x_{i}\}\) 方案数 \(ans\)：
\[\sum_{i=1}^{4}c_{i}x_{i}=S,\forall x_{i}\leq D_{i}
\]
若无视上界限制，则相当于完全背包求方案数。问题就在于每种硬币都有一个上界数量限制，此时按常规想法只能考虑分组背包。但还有一种想法——利用容斥原理将上界转化为下界
设满足下式的方案数为 \(U\)：
\[\sum_{i=1}^{4}c_{i}x_{i}=S
\]
满足下式的方案数为 \(V\)：
\[\sum_{i=1}^{4}c_{i}x_{i}=S,存在 x_{i}\geq D_{i}+1
\]
则显然：
\[ans = U - V
\]
上界转化为下界后，由于下界的“至少”那部分是必要的，因此可以在等式两侧直接抵消掉这一部分，进而转化为求下式的方案数：
\[\sum_{i=1}^{4}c_{i}x_{i}=S-\sum_{i\in I}c_{i}(D_{i}+1)，I为\{x_{i} \} 的某个子集
\]
\(U\) 可以用完全背包求方案数在 \(O(4S)\) 复杂度内预处理得到，而 \(V\) 实际上是 \(\{x_{i}\}\) 的并集大小，可以利用容斥原理转化为求所有子集的交集大小。而关键在于集合大小仅为 \(4\)，因此需要枚举的子集数量只有 \(2^{4} = 16\) 种。因此 \(V\) 可在 \(O(2^{4})\) 内得到。而总共有 \(n\) 个询问，故总复杂度 \(O(4S + 2^{4}n)\)。
code