Description
Data Constraint
Solution
这道题虽然加了随机化，但理论复杂度还是O(N^2)…… 我们可以将64位随机分成4块，然后我们每次选出不变的一块，对这一块与当前串完全相同的串与当前串进行匹配。
Code
using namespace std;
const int maxn=1.5e5+5,maxn1=65536;
int first[
maxn1*10],last[
maxn*5],next[
maxn*5],a[
maxn][
70],b[
10][
17];
int n,i,t,j,k,l,y,z,bz[70],ans,num,bz1[maxn*2];
ll x,er[70];
void lian(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);
scanf("%d",&n);er[1]=1;
for (i=2;i<=64;i++)er[i]=er[i-1]*2;
bz[0]=1;
for (i=1;i<=4;i++)
for (j=1;j<=16;j++){
x=0;
while (bz[x]) x=rand()d+1;
b[i][j]=x;bz[x]=1;
}
for (i=1;i<=n;i++){
scanf("%llu",&x);ans=0;
for (j=1;j<=64;j++)
if (er[j]&x) a[i][j]=1;
for (j=1;j<=4;j++){
y=0;
for (k=1;k<=16;k++)
if (er[b[j][k]]&x) y+=er[k];
z=y;
for (t=first[y+maxn1*(j-1)];t;t=next[t]){
y=last[t];l=0;
if (bz1[y]==i) continue;bz1[y]=i;
for (k=1;k<=64;k++)
if (a[y][k]!=a[i][k]){
l++;
if (l>3) break;
}
if (l==3) ans++;
}
lian(z+maxn1*(j-1),i);
}
printf("%d\n",ans);
}
}
