假设班里有 $_math_inline$10$math_inline_$ 个学生喜欢数学， $_math_inline$15$math_inline_$ 个学生喜欢语文， $_math_inline$21$math_inline_$ 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？
是 $_math_inline$10+15+21=46$math_inline_$ 个吗？不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢。
为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 $_math_inline$A,B,C$math_inline_$ 表示，则学生总数等于 $_math_inline$|A\cup B\cup C|$math_inline_$ 。
刚才已经讲过，如果把这三个集合的元素个数 $_math_inline$|A|,|B|,|C|$math_inline_$ 直接加起来，会有一些元素重复统计了，因此需要扣掉 $_math_inline$|A\cap B|,|B\cap C|,|C\cap A|$math_inline_$ ，但这样一来，又有一小部分多扣了，需要加回来，即 $_math_inline$|A\cap B\cap C|$math_inline_$ 。
即： $_math_inline$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$math_inline_$
把上述问题推广到一般情况，就是我们熟知的容斥原理。
容斥原理
设 U 中元素有 n 种不同的属性，而第 i 种属性称为 $_math_inline$P_i$math_inline_$ ，拥有属性 $_math_inline$P_i$math_inline_$ 的元素构成集合 $_math_inline$S_i$math_inline_$ ，那么
$_math_inline$ \begin{split} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i对于每个元素使用二项式定理计算其出现的次数。对于 $_math_inline$x$math_inline_$ ，假设它出现在 $_math_inline$T_1,T_2,\cdots,T_m$math_inline_$ 的集合中，那么它的出现次数为
$_math_inline$ \begin{split} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i补集
对于全集 U 下的 集合的并 可以使用容斥原理计算，而集合的交则用全集减去 补集的并集 求得：
$_math_inline$ \left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right| $math_inline_$右边使用容斥即可。
不定方程非负整数解计数
给出不定方程 $_math_inline$\sum_{i=1}^nx_i=m$math_inline_$ 和 n 个限制条件 $_math_inline$x_i\leq b_i$math_inline_$ ，其中 $_math_inline$m,b_i\leq \mathbb{N}$math_inline_$ . 求方程的非负整数解的个数
没有限制时
如果没有
$_math_inline$x_i 略证：插板法。 相当于你有 m 个球要分给 n 个盒子，允许某个盒子是空的。这个问题不能直接用组合数解决。 于是我们再加入 n-1 个球，于是问题就变成了在一个长度为 m+n-1 的球序列中选择 n-1 个球，然后这个 n-1 个球把这个序列隔成了 n 份，恰好可以一一对应放到 n 个盒子中。那么在 m+n-1 个球中选择 n-1 个球的方案数就是
$_math_inline$C_{m+n-1}^{n-1}$math_inline_$
。 接着我们尝试抽象出容斥原理的模型 目标：所有变量满足对应属性时集合的大小，即
$_math_inline$|\bigcap_{i=1}^nS_i|$math_inline_$
. 这个东西可以用
$_math_inline$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$math_inline_$
求解。
$_math_inline$|U|$math_inline_$
可以用组合数计算，后半部分自然使用容斥原理展开。 那么问题变成，对于一些
$_math_inline$\overline{S_{a_i}}$math_inline_$
的交集求大小。考虑
$_math_inline$\overline{S_{a_i}}$math_inline_$
的含义，表示
$_math_inline$x_{a_i}\geq b_{a_i}+1$math_inline_$
的解的数目。而交集表示同时满足这些条件。因此这个交集对应的不定方程中，有些变量有 下界限制 ，而有些则没有限制。 能否消除这些下界限制呢？既然要求的是非负整数解，而有些变量的下界又大于 0，那么我们直接 把这个下界减掉 ，就可以使得这些变量的下界变成 0，即没有下界啦。因此对于容斥模型
于是这个也可以组合数计算啦。这个长度为 k 的 a 数组相当于在枚举子集。
HAOI2008 硬币购物
4 种面值的硬币，第 i 种的面值是 $_math_inline$C_i$math_inline_$ 。n 次询问，每次询问给出每种硬币的数量 $_math_inline$D_i$math_inline_$ 和一个价格 $_math_inline$S$math_inline_$ ，问付款方式。
$_math_inline$n\leq 10^3,S\leq 10^5$math_inline_$
如果用背包做的话复杂度是 $_math_inline$O(4nS)$math_inline_$ ，无法承受。这道题最明显的特点就是硬币一共只有四种。抽象模型，其实就是让我们求方程 $_math_inline$\sum_{i=1}^4C_ix_i=S,x_i\leq D_i$math_inline_$ 的非负整数解的个数。
采用同样的容斥方式， $_math_inline$x_i$math_inline_$ 的属性为 $_math_inline$x_i\leq D_i$math_inline_$ . 套用容斥原理的公式，最后我们要求解
$_math_inline$ \sum_{i=1}^4C_ix_i=S-\sum_{i=1}^kC_{a_i}(D_{a_i}+1) $math_inline_$也就是无限背包问题。这个问题可以预处理，算上询问，总复杂度 $_math_inline$O(4S+2^4n)$math_inline_$ .
Code
1#include <bits/stdc++.h>
2
3using namespace std;
4const int S = 1e5 + 5;
5int c[5], d[5], n, s;
6long long f[S];
7
8int main() {
9
10 cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
11 f[0] = 1;
12 for (int j = 1; j <= 4; j++)
13 for (int i = 1; i < S; i++)
14 if (i >= c[j]) f[i] += f[i - c[j]];
15 for (int i = 1; i <= n; i++) {
16 cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
17 long long ans = 0;
18 for (int j = 1; j < 16; j++) {
19 int m = s, bit = 0;
20 for (int k = 1; k <= 4; k++)
21 if ((j >> (k - 1)) & 1) m -= (d[k] + 1) * c[k], bit++;
22 if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
23 }
24 cout << f[s] - ans << endl;
25 }
26 return 0;
27}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。