Description
Solution
这道题目十分的玄学，比赛时候就想到正解了（除了随机化的部分）。 暴力可以怎么做，可以先把数压成4位，然后每个位置存储与这个二进制相同的下标，然后暴力枚举。这样看起来就是
n2
的 由于数据是随机的（比赛的时候又告诉我1/3构造），所以我们压四位的时候，随机化一下，不要按顺序，这样就可以过了。 如果我1/3构造，全部都出相同的，这个方法就GG了，不知道出题人比赛的时候为什么要说这个不存在的东西。
Code
using namespace std;
typedef unsigned long long ll;
const
int maxn=
420000;
int i,j,k,l,t,n,
m,ans,o,
y,z;
int w[
5][
20],p[
80],a[maxn][
80],
q[5][
66000];
int first[maxn
*2],
last[maxn
*2],
next[maxn
*2],num,az[maxn];
bool bz[
100];
ll
x,er[
80];
int de(
int x,
int y){
return (
y-
1)
*4+
x;}
void add(
int x,
int y){
last[++num]=
y,
next[num]=first[
x],first[
x]=num;
}
int main(){
freopen(
"hashing.in",
"r",stdin);
freopen(
"hashing.out",
"w",stdout);
fo(i,
1,
4){
fo(j,
1,
16){
o=
rand()
d+
1;
while(bz[o])o=
rand()
d+
1;bz[o]=
1;
w[i][++w[i][
0]]=o;p[o]=i;
}
sort(w[i]+
1,w[i]+
17);
}
er[
0]=
1;fo(i,
1,
63)er[i]=er[i-
1]
*2;
scanf(
"%d",&n);
fo(i,
1,n){
scanf(
"%llu",&
x);ans=
0;
fo(j,
1,
64)
if(
x&er[j-
1])a[i][j]=
1;
fo(j,
1,
4){
y=
0;fo(k,
1,
16)
if(a[i][w[j][k]])
y+=er[k-
1];
rep(k,de(j,
y)){
z=
last[k]-
270000;o=
0;
if(az[z]==i)
continue;az[z]=i;
fo(l,
1,
64){
if(a[i][l]!=a[z][l])o++;
if(o>
3)
break;
}
if(o==
3)ans++;
}
add(de(j,
y),i+
270000);
}
printf(
"%d\n",ans);
}
}
