容斥原理
假设班里有 个学生喜欢数学， 个学生喜欢语文， 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？是 个吗？不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢。为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 表示，则学生总数等于 。刚才已经讲过，如果把这三个集合的元素个数 直接加起来，会有一些元素重复统计了，因此需要扣掉 ，但这样一来，又有一小部分多扣了，需要加回来，即 。即
一般地，对于任意多个集合，我们都可以列出这样一个等式，等式左边是所有集合的并的元素个数，右边是这些集合的各种搭配。每个搭配都是若干个集合的交集，且每一项前面的正负号取决于集合的个数————奇数个集合为正，偶数个集合为负。即
设 为有限集， ，则有
容斥原理在算法竞赛中的应用¶
例题BZOJ 1042[HAOI2008]硬币购物
题目大意：一共有 种硬币，面值分别为 。某人去买东西，去了 次。每次给出 ， 表示有 个面值为 的硬币，求购买价值为 的物品的付款方案数。
先用多重背包预处理出 ，表示不限制钞票数量购买价格为 的物品的方案数。由于容斥原理，我们最后的答案为
这样，我们就可以在 的时间复杂度内处理每个询问。
练习¶
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用