容斥定理
容斥定理:
计算几个集合并集的大小,先计算出所有单集合的大小,减去所有两个集合相交的部分,加上三个集合相交的部分,再减去四个集合相交的部分,以此类推,一只计算到所有集合相交的部分。
二进制枚举:
对于三个物品,我们有8种选择,对于n种物品,我们有2^n种选择,转化为二进制就是从0到2的n次方减一,就像是命题真假赋值一样。
#include <bies/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=0;i<(1<<n);i++)//从0到2的n次方-1
{
for(int j=0;j<n;j++)//判断第j个物品有没有被选中
{
cout<<1&(i>>j);
}
cout<<endl;
}
return 0;
}