标签: 容斥

2 篇文章

P3349 [ZJOI2016]小星星
题目链接:P3349 给定一棵 $n$ 个节点的树和一个 $n$ 个节点的图,要求为树上的每个节点映射到一个图上的节点(双射),且要求树上边对应图上也必须有相应的边,求方案数。 $n\leq 17$。 Sol 考虑朴素 DP,设 $F[i][j][k]$​ 表示将 $i$ 映射到 $j$,且 $i$ 的子树内的映射集合为 $k$ 的方案数。 瓶颈在…
浅谈容斥原理
容斥原理 定理: 设有 $n$ 个集合,第 $i$ 个集合为 $A_i$,则所有集合的并集可以表示成如下形式:$$|A_1\cup A_2\cup \cdots\cup A_n|=\sum_{i=1}^n (-1)^{i-1}\sum|A_1\cap A_2\cap\cdots\cap A_i|$$ 证明: 假设元素 $a$​ 被 $x$​ 个集合…