hash.同余.不過這里的同余不是普通意義上的同余.
#include <iostream>
#include <fstream>
using namespace std;
//ifstream fin("1.txt");
const int MAXN=100001;
const int mod=99991;
int n,k;
int c[MAXN][30];
int d[MAXN][30];
int h[mod];
int p[MAXN],len=0;
int s[MAXN];
int result=0;
inline int hashcode(const int id)
{
int s = 0;
for(int i=0; i<k; i++)
s=((s<<2)+(d[id][i]>>4))^(d[id][i]<<10);
s = s % mod;
s = s < 0 ? s + mod : s;
return s;
}
void find_hash(int x,int id)
{
int f[30];
bool ok=true;
for (int i=0;i<k;i++)
{
if (i==0) f[i]=c[id][i]-c[p[x]][i];
else
{
f[i]=c[id][i]-c[p[x]][i];
if (f[i]!=f[i-1]||f[i]==0) {ok=false;break;}
}
}
if (ok)
{
if (result<id-p[x])
{
result=id-p[x];
}
}
if (s[x]==-1)
{
len++;
s[x]=len;
s[len]=-1;
p[len]=id;
return;
}
else
{
find_hash(s[x],id);
}
}
void hash(int u,int id)
{
if (h[u]==-1)
{
len++;
h[u]=len;
s[len]=-1;
p[len]=id;
return;
}
find_hash(h[u],id);
}
int main()
{
cin>>n>>k;
if (n==1) {cout<<1<<endl;exit(0);}
memset(h,-1,sizeof(h));
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
int l=-1;
for (int j=0;j<k;j++)
{
int p=x%2;
l++;
c[i][l]=c[i-1][l]+p;
x/=2;
}
}
memcpy(d,c,sizeof(c));
for (int i=0;i<=n;i++)
{
int max=MAXN;
for (int j=0;j<k;j++)
{
if (max>d[i][j]) max=d[i][j];
}
for (int j=0;j<k;j++)
{
d[i][j]-=max;
}
int u=hashcode(i);
//cout<<u<<endl;
hash(u,i);
}
cout<<result<<endl;
// system("pause");
return 0;
}