引入

相信各位小学都学过容斥原理的三元版本，这里就不多赘述了。

模型

我们关注容斥原理的本质，其实就是求多个集合的并的大小。

令 $U$ 为全集，所有的 $S_i\subset U$。

下面把它拓展到 $n$ 元：

$|\bigcup_{i=1}^n S_i|=\sum_{m=1}^n(-1)^{m-1}\sum_{|a|=m,a_i<a_{i+1}}|\bigcap_{i=1}^m S_{a_i}|$

如果我们想求集合的交的大小，我们同样可以使用容斥原理，只需要套用下面的式子转化一下：

$|\bigcap_{i=1}^n S_i|=|U|-|\bigcup_{i=1}^n \overline{S_i}|$

重点是将其拓展到更一般的方面：

令 $U$ 为全集。
有 $n$ 个性质 $P_i$ 和 $n$ 个集合 $S_i$。
$\forall x\in U$，$x$ 具有 $P_i$ 性质 $\Leftrightarrow x\in S_i$。

则有：

$|\bigcap_{i=1}^n S_i|=|U|-\sum_{k=1}^n(-1)^{k-1}\sum_{|a|=k,a_i<a_{i+1}}|\bigcap_{i=1}^k \overline{S_{a_i}}|$

考察其意义。$\bigcap_{i=1}^n S_i$ 表示的是同时满足所有性质的元素数量，$\bigcap_{i=1}^k \overline{S_{a_i}}$ 表示的是 同时不满足性质 $P_{a_i}$ 的元素数量。

注意到非常好的一点是，等式的两边都是集合的交。

下面看几个应用。

不定方程解数量

有 $n$ 个变量 $x_i$，每个变量有限制形如 $0\leq x_i\leq b_i$，求 $\sum_{i=1}^n x_i=m$ 的解数量，$n$ 较小。

构造容斥模型。

我们把一组解 $(x_1,x_2,x_3,\cdots,x_n)$ 看做 $U$ 中的元素。
考虑先去掉 $x_i\leq b_i$ 的限制，令 $U$ 等于所有满足 $\sum_{i=1}^n x_i=m$ 的解的集合。
令性质 $P_i$ 为 $x_i\leq b_i$。

现在有了模型，直接套上容斥式子：

$|\bigcap_{i=1}^n S_i|=|U|-\sum_{k=1}^n(-1)^{k-1}\sum_{|a|=k,a_i<a_{i+1}}|\bigcap_{i=1}^k \overline{S_{a_i}}|$

其中 $|U|$ 使用插板法可求得 $|U|=\binom{n+m-1}{n-1}$，现在考虑怎么求 $\sum_{|a|=k,a_i<a_{i+1}}|\bigcap_{i=1}^k \overline{S_{a_i}}|$。

考虑其实际意义：$\overline{S_{i}}$ 中的 $x$ 不满足 $x_{i}\leq b_{i}$，也就是 $x_i\geq b_i+1$。若让所有 $\overline{S_{i}}$ 并起来，就是说 $x_{a_i}\geq b_{a_i}$，其余的满足 $x_i\geq 0$。这就变成了有下界不定方程解数量，我们是会的，答案是 $\binom{m-\sum(b_{a_i}+1)+n-1}{n-1}$。

所以，综合起一个式子，答案就是：

$\binom{n+m-1}{n-1}-\sum_{k=1}^n(-1)^{k-1}\sum_{|a|=k,a_i<a_{i+1}}\binom{m-\sum(b_{a_i}+1)+n-1}{n-1}$

朴素做，时间复杂度 $O(n2^n)$。

[HAOI2008] 硬币购物

一共有四种货币，面值是 $c_i$。$t$ 组询问，每次询问给你每种货币的数量和一个数 $s$，问用这些货币付 $s$ 块钱有多少种方案。

跟上面那个挺像的，是不是。直接构造容斥模型：

我们把一组解 $(x_1,x_2,x_3,x_4)$ 看做全集 $U$ 中的元素。
考虑先去掉上界的限制，令全集 $U$ 为所有满足 $\sum_{i=1}^4c_ix_i=s$ 的 $(x_1,x_2,x_3,x_4)$。
令性质 $P_i$ 为 $x_i\leq d_i$。

还是先考虑全集 $U$ 是什么，是不是直接就是一个完全背包？

然后考虑怎么求后边那些，是不是就是某些货币有下界，有的没有？我们先把有下界那些强制选上，剩下的是不是又是一个完全背包？

令 $f_i$ 为四种货币无限量，付 $i$ 块钱的方案数，则答案就是：

$f_s-\sum_{k=1}^4 (-1)^{k-1} \sum_{|a|=k,a_i<a_{i+1}}f_{s-\sum_{i=1}^k c_{a_i}d_{a_i}}$

直接做这个式子就好了。