容斥原理

数学表达

|A1A2A3......An|
=1in|Ai|1i<jn|AiAj|+1i<j<kn|AiAjAk|
+...+(1)n1|A1A2A3...Ak|

也可以表达为:

|ni=1Ai|
=nk=1(1)k11i1<i2<i3...<inn|Ai1Ai2Ai3...Aik|


我们知道,统计并集大小往往较难,此时,我们可以通过容斥原理将并集关系通过交集关系表示出来。

容斥原理


容斥原理