IDEA激活码
文章目录
- 一、 容斥原理
- 二、 容斥原理 示例
一、 容斥原理
A
1
,
A
2
,
⋯
,
A
n
A_1 , A_2 , \cdots , A_n
A1,A2,⋯,An 是
n
n
n 个集合 ; 则 这
n
n
n 个集合 并集的元素个数 是 :
∣
⋃
i
=
1
n
A
i
∣
=
∑
i
=
1
n
∣
A
i
∣
−
∑
i
<
j
∣
A
i
∩
A
j
∣
+
∑
i
<
j
<
k
∣
A
i
∩
A
j
∩
A
k
∣
−
⋯
+
(
−
1
)
n
−
1
∣
A
1
∩
A
2
∩
⋯
∩
A
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 |
∣i=1⋃nAi∣=i=1∑n∣Ai∣−i<j∑∣Ai∩Aj∣+i<j<k∑∣Ai∩Aj∩Ak∣−⋯+(−1)n−1∣A1∩A2∩⋯∩An∣
解析 :
n
n
n 个集合进行并运算后 , 元素个数 , 通常使用 容斥原理 进行计算 ;
∑
i
=
1
n
∣
A
i
∣
\sum_{i = 1}^n | A_i |
∑i=1n∣Ai∣ : 将每个集合中的 元素个数 相加 , 该值大于 总元素数 , 需要进行修正 ; ( 系数值
(
−
1
)
0
(-1)^0
(−1)0 )
∑
i
<
j
∣
A
i
∩
A
j
∣
\sum_{i < j} | A_i \cap A_j |
∑i<j∣Ai∩Aj∣ : 减去两两相交的元素个数 , 该值又小于 总元素数 , 继续进行修正 ; ( 系数值
(
−
1
)
1
(-1)^1
(−1)1 )
∑
i
<
j
<
k
∣
A
i
∩
A
j
∩
A
k
∣
\sum_{i < j < k} | A_i \cap A_j \cap A_k |
∑i<j<k∣Ai∩Aj∩Ak∣ : 加上三个集合相交的元素个数 , 该值大于 总元素数 , 继续进行修正 ; ( 系数值
(
−
1
)
2
(-1)^2
(−1)2 )
减去四个集合相交的元素个数 , 该值小于 总元素数 , 继续进行修正 ; ( 系数值
(
−
1
)
3
(-1)^3
(−1)3 )
⋮
\vdots
⋮
(
−
1
)
n
−
1
∣
A
1
∩
A
2
∩
⋯
∩
A
n
∣
( -1 )^{n - 1} | A_1 \cap A_2 \cap \cdots \cap An |
(−1)n−1∣A1∩A2∩⋯∩An∣ : 加上
(
−
1
)
n
−
1
( -1 )^{n - 1}
(−1)n−1 乘以
n
−
1
n-1
n−1 个集合相交的元素个数 ; ( 系数值
(
−
1
)
n
−
1
(-1)^{n-1}
(−1)n−1 )
上述 奇数个集合 交集元素个数 前系数是 正数 , 偶数个集合 交集元素个数 前系数是 负数 ;
二、 容斥原理 示例
1
1
1 ~
10000
10000
10000 之间 , 既不是某个整数的平方 , 又不是某个整数的立方 , 的数个数 ?
全集 :
E
E
E 集合是全集 , 是
1
1
1 到
10000
10000
10000 的自然数 ,
E
E
E 集合的个数
∣
E
∣
=
10000
|E| = 10000
∣E∣=10000
平方对应的数集合
A
A
A :
A
A
A 集合是 某个数 的平方 对应的 某个数 集合 ,
A
=
{
x
∈
E
∣
x
=
k
2
∧
k
∈
Z
}
A = \{ x \in E | x = k^2 \land k \in Z \}
A={x∈E∣x=k2∧k∈Z} ,
A
A
A 集合元素个数是
∣
100
∣
|100|
∣100∣ ;
10
0
2
=
10000
100^2 = 10000
1002=10000 , 因此
A
A
A 集合的元素是
{
0
,
1
,
2
,
⋯
,
100
}
\{0, 1, 2 , \cdots , 100 \}
{0,1,2,⋯,100} , 元素个数有
100
100
100 个 ;
1
2
,
2
2
,
3
3
,
⋯
,
10
0
2
1^2 , 2^2 , 3^3, \cdots ,100^2
12,22,33,⋯,1002 都在
1
1
1 到
10000
10000
10000 之间 ,
10
1
2
=
10201
101^2 = 10201
1012=10201 就超过
10000
10000
10000 了 ;
立方对应的数集合
B
B
B :
B
B
B 集合是 某个数 的立方 对应的 某个数 集合 ,
B
=
{
x
∈
E
∣
x
=
k
3
∧
k
∈
Z
}
B = \{ x \in E | x = k^3 \land k \in Z \}
B={x∈E∣x=k3∧k∈Z} ,
A
A
A 集合元素个数是
∣
21
∣
|21|
∣21∣ ;
2
1
3
=
9261
21^3 = 9261
213=9261 , 因此
B
B
B 集合的元素是
{
0
,
1
,
2
,
⋯
,
21
}
\{0, 1, 2 , \cdots , 21 \}
{0,1,2,⋯,21} , 元素个数有
21
21
21 个 ;
1
3
,
2
3
,
3
3
,
⋯
,
2
1
3
1^3 , 2^3 , 3^3, \cdots ,21^3
13,23,33,⋯,213 都在
1
1
1 到
10000
10000
10000 之间 ,
2
2
2
=
10648
22^2 = 10648
222=10648 就超过
10000
10000
10000 了 ;
计算
A
∩
B
A \cap B
A∩B 集合的交集
C
C
C : 元素个数 , 既是平方 , 又是立方 , 肯定是六次方的数 ,
C
=
{
x
∈
E
∣
x
=
k
6
∧
k
∈
Z
}
C= \{ x \in E | x = k^6 \land k \in Z \}
C={x∈E∣x=k6∧k∈Z} ,
C
C
C 集合的元素个数是
4
4
4 ;
4
6
=
4096
4^6 = 4096
46=4096 , 因此
C
C
C 集合的元素是
{
1
,
2
,
3
,
4
}
\{1, 2 , 3, 4\}
{1,2,3,4} , 元素个数有
4
4
4 个 ;
1
6
,
2
6
,
3
6
,
4
6
1^6 , 2^6 , 3^6, 4^6
16,26,36,46 都在
1
1
1 到
10000
10000
10000 之间 ,
5
6
=
15
,
625
5^6 = 15,625
56=15,625 就超过
10000
10000
10000 了 ;
题目可以转化成 : 集合
Z
Z
Z 中 , 既不属于
A
A
A 集合 , 有不属于
B
B
B 集合 的数字 ;
集合
A
A
A 与 集合
B
B
B 并集是
A
∪
B
A \cup B
A∪B
上述并集 的 绝对补集
∼
(
A
∪
B
)
\sim ( A \cup B )
∼(A∪B) 元素个数
∣
∼
(
A
∪
B
)
∣
|\sim ( A \cup B ) |
∣∼(A∪B)∣ , 就是题目中要求的结果 ;
∣
∼
(
A
∪
B
)
∣
=
∣
E
∣
−
∣
A
∪
B
∣
|\sim ( A \cup B ) | = |E| - |A \cup B|
∣∼(A∪B)∣=∣E∣−∣A∪B∣
上述式子中 ,
∣
E
∣
=
10000
|E| = 10000
∣E∣=10000 ,
∣
A
∪
B
∣
|A \cup B|
∣A∪B∣ 值可以使用 容斥原理 进行计算 ;
∣
A
∪
B
∣
|A \cup B|
∣A∪B∣ 两个集合并集的元素个数 , 可以使用两个集合的元素个数相加 , 然后减去两个集合交集的元素个数 ;
∣
A
∪
B
∣
=
∣
A
∣
+
∣
B
∣
−
∣
A
∪
B
∣
=
100
+
21
−
4
=
117
|A \cup B| = |A| + |B| - |A \cup B| = 100 + 21 - 4 = 117
∣A∪B∣=∣A∣+∣B∣−∣A∪B∣=100+21−4=117
代入总的公式 :
∣
∼
(
A
∪
B
)
∣
=
∣
E
∣
−
∣
A
∪
B
∣
=
10000
−
117
=
9883
|\sim ( A \cup B ) | = |E| - |A \cup B| = 10000 - 117 = 9883
∣∼(A∪B)∣=∣E∣−∣A∪B∣=10000−117=9883
