首页 > 代码库 > 【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix

【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix

引用题解:http://blog.csdn.net/popoqqq/article/details/41084047

#include<cstdio>#include<cstring>using namespace std;typedef unsigned long long ull;int n,m,a,b,q;const ull seed1=17,seed2=19;#define MOD 1000001ull v[MOD],sum[1001][1001],ord[201],pow1[1001],pow2[1001];char s[1001][1001];int first[MOD],next[MOD],en;void Insert(const ull &V){	int U=(int)(V%MOD);	v[en]=V;	next[en]=first[U];	first[U]=en++;}int main(){	scanf("%d%d%d%d",&n,&m,&a,&b);	memset(first,-1,sizeof(first));	ord[‘0‘]=1,ord[‘1‘]=2;	for(int i=1;i<=n;++i)	  scanf("%s",s[i]+1);	for(int i=1;i<=n;++i)	  for(int j=1;j<=m;++j)	    sum[i][j]=ord[s[i][j]]+sum[i-1][j]*seed1;	for(int i=1;i<=n;++i)	  for(int j=1;j<=m;++j)	    sum[i][j]+=sum[i][j-1]*seed2;	pow1[0]=pow2[0]=1;    for(int i=1;i<=n;i++) pow1[i]=pow1[i-1]*seed1;    for(int i=1;i<=m;i++) pow2[i]=pow2[i-1]*seed2;    for(int i=a;i<=m;i++)	  for(int j=b;j<=n;j++)	    Insert(sum[i][j]		-sum[i-a][j]*pow1[a]		-sum[i][j-b]*pow2[b]		+sum[i-a][j-b]*pow1[a]*pow2[b]);	scanf("%d",&q);	for(;q;--q)        {          for(int i=1;i<=a;i++) scanf("%s",s[i]+1);         for(int i=1;i<=a;i++)            for(int j=1;j<=b;j++)              sum[i][j]=ord[s[i][j]]+sum[i-1][j]*seed1;          for(int i=1;i<=a;i++)            for(int j=1;j<=b;j++)              sum[i][j]+=sum[i][j-1]*seed2;        int o=(int)(sum[a][b]%MOD);        for(int i=first[o];i!=-1;i=next[i]) if(v[i]==sum[a][b]) {puts("1"); goto OUT;}        puts("0"); OUT:;      }  	return 0;}

【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix