\(\color{purple}\text{P5123 [USACO18DEC]Cowpatibility G}\)
题意
每只集合有五个值，求交集为零的两个集合的对数。
解法
首先正难则反，我们考虑求出交集不为零的两个集合的对数 \(sum\)，则 \(ans=\frac{n\times (n-1)}{2}-sum\) 。
如何求出交集不为零的两个集合的对数？
我们考虑容斥。设目前求与集合 \(a\) 的交集不为零的集合个数，那么答案就是 “拥有 \(a_1\) 的集合个数 \(+\) 拥有 \(a_2\) 的集合个数 \(+\) 拥有 \(a_3\) 的集合个数 \(-\) 拥有 \(a_1a_2\) 的集合个数 \(-\) 拥有 \(a_2a_3\) 的集合个数 \(-\) 拥有 \(a_1a_3\) 的集合个数 \(+\) 拥有 \(a_1a_2a_3\) 的集合个数”（这是三元素的情况，原题目有五元素）
如何求出拥有元素 “\(a_ia_j\dots\)” 的集合个数？
显然集合的种类太多了，我们把不必要的省去，只统计出现过的，就要用到 hash ，但是这是一个多元素的 \(hash\) ，我们可以用集合拥有的元素按一定的值乘构成 \(hash\) 值映射。
枚举的时候用二进制来表示元素有无比较方便
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,p=1e6+7;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
struct HASH{
int tot=0,r[5][N],head[p+10],last[N],val[N];
void add(int a[]){
int ys=0;
for(int i=0;i<5;i++)ys=(ys*233+a[i])%p;
for(int i=head[ys];i;i=last[i]){
if(r[0][i]==a[0] && r[1][i]==a[1] && r[2][i]==a[2] && r[3][i]==a[3] && r[4][i]==a[4]){
val[i]++;return;
}
}
tot++;
last[tot]=head[ys],head[ys]=tot;val[tot]++;
for(int i=0;i<5;i++)r[i][tot]=a[i];
return;
}
int query(int a[]){
int ys=0;
for(int i=0;i<5;i++)ys=(ys*233+a[i])%p;
for(int i=head[ys];i;i=last[i]){
if(r[0][i]==a[0] && r[1][i]==a[1] && r[2][i]==a[2] && r[3][i]==a[3] && r[4][i]==a[4])
return val[i];
}
return 0;
}
}H;
int n,ans;
int e[N][5];
void bark(int x){
while(x){
cout<<x%2;
x/=2;
}
return;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
for(int j=0;j<5;j++)e[i][j]=read();
sort(e[i],e[i]+5);
}
int tmp[5],z=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=(1<<5)-1;j++){
for(int k=0;k<5;k++)tmp[k]=0;z=0;
for(int k=0;k<5;k++)
if((j&(1<<k))!=0)
tmp[z++]=e[i][k];
H.add(tmp);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=(1<<5)-1;j++){
for(int k=0;k<5;k++)tmp[k]=0;z=0;
for(int k=0;k<5;k++)
if((j&(1<<k))!=0)
tmp[z++]=e[i][k];
if(z%2==1)ans+=H.query(tmp)-1;
else ans-=H.query(tmp)-1;
}
}
printf("%lld\n",n*(n-1)/2-ans/2);
return 0;
}