题解P5123
simonG
·
·
题解
前言
题意：求两两集合间没有交集的对数。
一看涉及集合计数，考虑容斥原理。
详解
先把答案赋值为 n(n-1)，即总共的对数。
枚举 S_i ，答案减去与 S_j(j<i) 有交集的对数。
对于集合 S_i=\{a,b,c\} ，（此处把 m 设为3）
设 cnt_i 数组为含有i元素的集合个数。
那么与S_i有交集的集合个数为（容斥原理）：
用总答案减去上式即可。
$m=5$ 也同理：我们发现上面的 $cnt$ 中的下标对应的是每个元素的出现与不出现。
这样就可以使用二进制枚举的方法。
用二进制中的第 $i$ 位表示第 $i$ 个数的出现与否。
当出现了奇数个元素时，对贡献为正；否则为负。
但是如何存储 $cnt$ 数组呢？用哈希表或 STL ```map``` 即可。
这里使用字符串存储。
### 代码
```cpp
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
long long n,ans;
string a[7];
map<string,long long> f;
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
for(int j=1; j<=5; j++) cin>>a[j];
sort(a+1,a+6);
for(int j=1; j<32; j++) {//利用二进制枚举哪些数被选
int cnt=0;
string s="";
for(int k=1;k<=5;k++)
if(j&(1<<(k-1))) {
cnt++;
s+=a[k]+" ";
} //用字符串存储方案
if(cnt&1) ans+=f[s];
else ans-=f[s];
f[s]++;
}
}
printf("%lld\n",n*(n-1)/2-ans);
return 0;
}
```
应该是较短的代码。