容斥原理是解决这一类问题的：有\(N\)个集合\(S_1,S_2,\dots,S_N\)，求\(|\bigcup\limits_{i=1}^{N}S_i|\)。首先我们看这个\(N=2\)时的问题：这时很明显答案为\(|A|+|B|-|A\bigcapB|\)。以下是\(N=3\)时的样子：此时答案显然为\(|A|+|B|+|C|-|A\bigcapB|-|A\bigcapC

10.容斥原理拓展10.1二项式反演\[P.10.1(1)\]设\(U=\{S_1,S_2,S_3...S_n\}\)，且任意\(i\)个元素的交集都相等定义\(g(x)\)为\(x\)个集合的交集，\(f(x)\)为\(x\)个集合补集的交集（定义\(f(0)=g(0)=U\)），则：\[\mid\bigcap^{n}_{i}S_{i}\mid=\midU\mid+\sum_{i}\{(-1)^{

继数论和组合之后的第三大数学巨坑，高中数学必修and选修联合起来！基本概念和符号表述该部分可参考必修二（人教版）最后一章，本质上是使用集合描述概率随机事件：满足下列条件的现象可以在相同的条件下重复进行实验结果不止一个，且所有结果可以事先预知实验前不确定出现什么结果

这份知识点总结（cheatsheet）是基于21年入学直博的师兄的押题（因为我没太听课

目录容斥原理Min-Max容斥广义容斥原理容斥原理原理：\[|\bigcup_{i=1}^nA_i|=\sum_{j=1}^n(-1)^{j-1}\sum_{a_k\not=a_{k+1}}\bigcap_{l=1}^mA_{a_i}\]这东西学过小学奥数就会了。一些有用的结论：\[|\bigcap_{i=1}^nA_i|=|\Omega|-|\bigcup_{i=1}^n\overline{A_i

期望事件事件\((event)\)，通常用\(E\)来表示。写法：用大写字母\(A,B,C....\)来表示。\(A\bigcapB\A\)和\(B\)同时发生\(A\bigcupB\A\)和\(B\)的和减去他们重叠的部分。\(\overlineA\)不在\(A\)处的\(\Omega\)全体不难发现，当一个群体的一个事件为\(A\)，那么\(\Omega\)

1.容斥原理1.1介绍解决集合内计数问题。\(S\)为集合编号集合。\[\left|\bigcup_{i\inS}A_i\right|=\sum_{T\subseteqS\wedgeT\ne\varnothing}^{n}(-1)^{(\left|T\right|-1)}\left|\bigcap_{j\inT}A_j\right|\]1.2咕咕咕

题目描述九条可怜是一个喜欢树的女孩子，她想生成两棵均有\(n\)个节点的树。第一棵树的生成方式是：节点\(1\)作为树的根。对于\(i\in[2,n]\)，从\([1,i-1]\)

\(\mathcalPreface\)可能容斥原理的公式等还是\(AK\IOI\)的巨佬讲得详细，大家可以看看这篇博客。这篇博客把我写得手废了。我这个里这接上公式：\[|\bigcup\limits_{i

三个知名\(\text{NP}\)问题：「\(\rm{k}\)-染色问题」「二分图完美匹配计数」「\(\rm{k}\)-路径问题」。虽然目前还没有多项式算法，但是三者都存在\(O(2^n\rm{poly}(n))\)