学步园

hash存储，查询，跟POJ 3349类似

#include<stdio.h>
#include<stdlib.h>;
#include<string.h>
#define inf 100001
struct Edge{
	int pos[32],next;
}edge[100100];
int head[100100],max,num[100100],k;
int Max(int a,int b){
	return a>b?a:b;
}
int add(int b,int pos){
	int i,j;
	int hash=b%inf;
	for(i=head[hash];i!=-1;i=edge[i].next){
		if(b==num[i]){
			bool flag=0;
			int len=edge[pos].pos[1]-edge[i].pos[1];
			for(j=2;j<=k;j++)
				if(edge[pos].pos[j]-edge[i].pos[j]!=len){
					flag=1;
					break;
				}
			if(!flag)
				return i;
		}	
	}
	edge[pos].next=head[hash];
	head[hash]=pos;
	return pos;
}
int main(){
	int i,j,n,tem;
	memset(head,-1,sizeof(head));
	scanf("%d %d",&n,&k);
	int mod=(1<<k)-1;
	for(i=1;i<=k;i++)
		edge[0].pos[i]=0;
	num[0]=0;
	max=0-add(0,0);
	for(i=1;i<=n;i++){
		scanf("%d",&tem);
		num[i]=(num[i-1]+tem)%mod;
		for(j=1;j<=k;j++){
			if(tem&(1<<(j-1)))
				edge[i].pos[j]=edge[i-1].pos[j]+1;
			else
				edge[i].pos[j]=edge[i-1].pos[j];
		}
		int temp=add(num[i],i);
		max=Max(max,i-temp);
	}
	printf("%d\n",max);
	return 0;
}