基础

约 92 个字 15 行代码

讲课链接

多个有交集的集合计算并集

原理

三个子集 $S_0,S_1,S_2$ 的各种交集可以表示为

$$|S_0\cup S_1\cup S_2|=|S_0|+|S_1|+|S_2|-|S_0\cap S_1|-|S_1\cap S_2|-|S_2\cap S_0|+|S_0\cap S_1\cap S_2|$$

可以另表示为

$$+001+010+100-011-110-101+111$$

代码

可以dfs优化成2^n

设子集个数有 $x$ 个

//bit确定加减，situation是情况总数
int bit,situation=1<<x;
for(int i=1;i<situation;++i)
{
    bit=-1;
    for(int j=0;j<x;++j)
    {
        if((i>>j)&1)
        {

            bit=-bit;
        }
    }
    bit*
}