容斥原理

容斥原理

描述

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

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

2016-12-28 / 3 min read