题目大意
给出一些64位整数，对每个数球前面和它二进制不同位刚好为三位的数有多少个。
解题思路
首先我们发现位和位之间是独立的，先随机化打乱顺序。因为要求三位不同，把原数分成四份，至少有一位相同，我们用一个桶来维护。因为随机化过，所以数期望是平均分配的，用平方级别扫描可以通过。最后需要判一下之前是否有计算过相同数对。
code
using namespace std;
int const mn=1.5
*1e5+9,mp=7*1e4+9,mp2=6*1e5+9,inf=1e9+7;
int n,b[
70],c[
70],gra[
5],begin[
5][
mp],to[
5][
mp2],next[
5][
mp2];
ULL a[
mn][
5];
void insert(int u,int v,int w){
to[u][++gra[u]]=w;
next[u][gra[u]]=begin[u][v];
begin[u][v]=gra[u];
}
int main(){
freopen("hashing.in","r",stdin);
freopen("hashing.out","w",stdout);
scanf("%d",&n);
srand(n);
fo(i,1,64){
b[i]=i;
int tmp=rand()%i+1;
swap(b[i],b[tmp]);
}
fo(i,1,n){
scanf("%llu",&a[i][0]);
ULL tmp=a[i][0];
fo(j,1,64)c[j]=tmp&1,tmp>>=1;
fo(j,1,64){
int k=((j-1)>>4)+1;
a[i][k]=(a[i][k]<<1)+c[b[j]];
}
fo(j,1,4)insert(j,a[i][j],i);
int ans=0;
fo(j,1,4)fr(k,j,a[i][j]){
int ok=1;
fo(l,1,j-1)if(!(a[to[j][k]][l]^a[i][l])){ok=0;break;}
if(!ok)continue;
int tmp=0;
fo(l,1,4){
int tmp2=a[to[j][k]][l]^a[i][l];
while(tmp2)
tmp++,tmp2-=tmp2&(-tmp2);
}
if(tmp==3)
ans++;
}
printf("%d\n",ans);
}
return 0;
}
