原来容斥分为两种 一种是普通容斥 一种是广义容斥。两种都挺重要的 广义容斥的题目较多。
那就 先说普通容斥吧。
容斥 就是简单进行 计数问题的东西 大体上就是把重复的减去 最后发现没有重复的东西了。
上道例题感受一下吧：
BZOJ4665 这道题看起来很精辟的样子... 简单分析一下吧。
n个人 n种喜糖 n个人互相交换喜糖 问有多少种方案使得每个人手中的糖的种类和原来不一样。
两种方案不同当且仅当存在一个人他的糖的种类在两个方案种是不一样的。
初始情况每个人手中的糖可能相等可能不相等。
这道题 虽然是求方案数 但是 方案数和最后的情况有关 我们直接求最后的情况即可。
那么也就是 有多少个本质不同的答案使得 每个人手中的糖和原来不同。
由于可能两个人初始情况 可能拥有相同的糖 所以这两个人的交换显然是无效的...
可以爆搜... 考虑怎么求 答案。只能上容斥了 因为没有什么比较好的办法了。
update:看了很多题解才真正理解 题解里的东西 很多题解都没有阐述为什么？而是只是一味的说怎么做 我觉得这是极其不好的 做完跟没做一样。
那么我们就需要计算 有k个人拿到了和原来一样的糖了 显然由于每一种糖对应一些人 所以我们利用dp来进行计数.
f[i][j]表示 前i种糖 有j个人拿到了和原来相同的糖了 转移十分显然。
但是 出现的小问题是 我们想要容斥 总方案数是多少呢？这是一个错排问题。但是存在若干个数字是相同的 又不是错排问题了 所以我们发现总方案数也很棘手。
我没想通 要怎么做 但是可以给出题解的做法。
强行认为 糖果颜色相同但是本质不同 那么转移有 f[i][j]+=f[i-1][k]C(cnt[i],j-k)(cnt[i]-1)... 后面乘一个下降幂 最后 f[m][i]
原文：https://www.cnblogs.com/chdy/p/12318065.html