AFuture's Blog

描述

容斥原理的简单描述如下：

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。简单的说，就是对所有单个集合求和后减去单数个集合相交部分，加上双数集合相交部分。

定义：

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

抽屉原理简述：

第一抽屉原理：

1. 把多于n+k个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
2. 把多于mn(m乘以n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
3. 把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。

第二抽屉原理：

1. 把$（mn－1）$个物体放入n个抽屉中，其中必有一个抽屉中至多有$（m—1）$个物体 (例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。

在数论中，裴蜀等式（Bézout's identity） 或 裴蜀定理 是一个关于最大公因数的定理：

对于正整数 a, b，存在s,t∈Z 使 sa + t b = gcd (a,b) 成立。