文章目录
一、 容斥原理
A_1 , A_2 , cdots , A_n 是
n 个集合 ; 则 这
n 个集合 并集的元素个数 是 :
| bigcup_{i=1}^{n} A_i | = sum_{i = 1}^n | A_i | - sum_{i < j} | A_i cap A_j | sum_{i < j < k} | A_i cap A_j cap A_k | - cdots ( -1 )^{n - 1} | A_1 cap A_2 cap cdots cap An |解析 :
n 个集合进行并运算后 , 元素个数 , 通常使用 容斥原理 进行计算 ;
sum_{i = 1}^n | A_i | : 将每个集合中的 元素个数 相加 , 该值大于 总元素数 , 需要进行修正 ; ( 系数值
(-1)^0 )
sum_{i < j} | A_i cap A_j | : 减去两两相交的元素个数 , 该值又小于 总元素数 , 继续进行修正 ; ( 系数值
(-1)^1 )
sum_{i < j < k} | A_i cap A_j cap A_k | : 加上三个集合相交的元素个数 , 该值大于 总元素数 , 继续进行修正 ; ( 系数值
(-1)^2 )
减去四个集合相交的元素个数 , 该值小于 总元素数 , 继续进行修正 ; ( 系数值
(-1)^3 )
vdots( -1 )^{n - 1} | A_1 cap A_2 cap cdots cap An | : 加上
( -1 )^{n - 1} 乘以
n-1 个集合相交的元素个数 ; ( 系数值
(-1)^{n-1} )
上述 奇数个集合 交集元素个数 前系数是 正数 , 偶数个集合 交集元素个数 前系数是 负数 ;
二、 容斥原理 示例
1 ~
10000 之间 , 既不是某个整数的平方 , 又不是某个整数的立方 , 的数个数 ?
全集 :
E 集合是全集 , 是
1 到
10000 的自然数 ,
E 集合的个数
|E| = 10000平方对应的数集合
A :
A 集合是 某个数 的平方 对应的 某个数 集合 ,
A = { x in E | x = k^2 land k in Z } ,
A 集合元素个数是
|100| ;
100^2 = 10000 , 因此
A 集合的元素是
{0, 1, 2 , cdots , 100 } , 元素个数有
100 个 ;
1^2 , 2^2 , 3^3, cdots ,100^2 都在
1 到
10000 之间 ,
101^2 = 10201 就超过
10000 了 ;
立方对应的数集合
B :
B 集合是 某个数 的立方 对应的 某个数 集合 ,
B = { x in E | x = k^3 land k in Z } ,
A 集合元素个数是
|21| ;
21^3 = 9261 , 因此
B 集合的元素是
{0, 1, 2 , cdots , 21 } , 元素个数有
21 个 ;
1^3 , 2^3 , 3^3, cdots ,21^3 都在
1 到
10000 之间 ,
22^2 = 10648 就超过
10000 了 ;
计算
A cap B 集合的交集
C : 元素个数 , 既是平方 , 又是立方 , 肯定是六次方的数 ,
C= { x in E | x = k^6 land k in Z } ,
C 集合的元素个数是
4 ;
4^6 = 4096 , 因此
C 集合的元素是
{1, 2 , 3, 4} , 元素个数有
4 个 ;
1^6 , 2^6 , 3^6, 4^6 都在
1 到
10000 之间 ,
5^6 = 15,625 就超过
10000 了 ;
题目可以转化成 : 集合
Z 中 , 既不属于
A 集合 , 有不属于
B 集合 的数字 ;
集合
A 与 集合
B 并集是
A cup B上述并集 的 绝对补集
sim ( A cup B ) 元素个数
|sim ( A cup B ) | , 就是题目中要求的结果 ;
|sim ( A cup B ) | = |E| - |A cup B|上述式子中 ,
|E| = 10000 ,
|A cup B| 值可以使用 容斥原理 进行计算 ;
|A cup B| 两个集合并集的元素个数 , 可以使用两个集合的元素个数相加 , 然后减去两个集合交集的元素个数 ;
|A cup B| = |A| |B| - |A cup B| = 100 21 - 4 = 117代入总的公式 :
|sim ( A cup B ) | = |E| - |A cup B| = 10000 - 117 = 9883
