容斥原理学习笔记
__graphite__
·
·
算法·理论
一个很重要的东西
首先为了方便我们规定
0^0=1
也就是说
0^n=\left[n=0\right]
你们可能会说：“啊火神这个 [] 是啥啊？”
[P]称为Iverson括号，P是一个命题，若P为真则[P]=1,否则[P]=0。
OIer 话：类似 bool。
这个规定超级有用，有用在哪你们待会就知道了。
朴素集合论
“这玩意跟容斥有什么关系？”
相信这是很多没有学过的人的疑问。
很简单：你待会要用。
定义
一个集合是一些对象构成的整体。这些对象称为集合的元素。
一般采用如下记号：
S=\{x|P(x)\}
表示满足性质P的对象构成的集合。
很晕对吧？待会你会更晕，建议多读几遍这部分。
集合，但是运算？
集合中对象的数量称为集合的大小，记为|S|。
若x是S中的对象之一，称x属于S,记为x \in S。
称右边的集合为两集合的交集：A \cap B=\{x|x \in A \land x \in B\}
称右边的集合为两集合的并集：A \cup B=\{x|x \in A \lor x \in B\}
称右边的集合为两集合的差或补：A \setminus B=\{x|x∈A \land x \not\in B\}
开始步入正轨：组合数
已经自动帮你省流部分：小学数学，杨辉三角。
快感谢我！
唯一要说的是他的记号：
\dbinom{n}{m}=\dbinom{n}{n-m}=C_n^m=C_n^{n-m}
达成挑战：二项式定理（发现二项式定理并学会使用）
(1+x)^n=\sum\limits_{i=0}^n\dbinom{n}{i}x^i
然后是一个重要组合恒等式
它叫 ——Theorem！
\sum_{i=0}^{n} (-1)^i\binom{n}{i} =\left [ n=0 \right ]
容斥，它来辣！
其实挺简单的（？
先来一道辣几题（TB 音）
一次模拟赛，一个班上有 10 个人，5 个人过了 T1,3 个人过了 T2, 1 个人过了两道题，问有多少人过了题。
答案是 5+3-1=7。
waterful 对吧。
结论
更一般的结论是：
一个难一点的问题
现在有n个元素，以及m条限制P_1,P_2,…,P_m,求有多少个元素满足所有的限制。
这里介绍“减法原理”：
转化为n减去至少违反了一条限制的元素数量。令S_i=\{x|x违反P_i\},那么减去的部分就是所有S_i的并集大小。
上一个问题的延伸
全错排问题！是什么我就不说啦（真的只是字面意思）！
提到它不是要解，而是它和上一题几乎一样！
相当于 所有全排列数量-有i=p_i的排列数量。
再用上“更一般的结论”好吧直接 AC！
k 错排问题的话有了结论读者自证不难。
欧拉函数
待会做题要用。
$$
\varphi(n)=\prod\limits_{}^{}(1-\frac{1}{p_i})
$$
### 例题
[https://www.luogu.com.cn/problem/AT_arc101_c](https://www.luogu.com.cn/problem/AT_arc101_c)
[https://www.luogu.com.cn/problem/SP7685](https://www.luogu.com.cn/problem/SP7685)
[https://www.luogu.com.cn/problem/AT_abc241_h](https://www.luogu.com.cn/problem/AT_abc241_h)
[https://www.luogu.com.cn/problem/AT_abc236_h](https://www.luogu.com.cn/problem/AT_abc236_h)
### 结语
又是一篇我挺满意的学习笔记，但总感觉自己讲的不清楚...
这可能是我自 CSP 失利后第一次再次学习新知识。
感谢所有人那段至暗时刻对我的支持！
另，若有添加知识点的建议私信我，或在此博客评论发。