题目

题目

思路

怎么可能是Hash

结果就是Hash，亏我想了一下午的数据结构(╯‵□′)╯︵┻━┻。

首先，这道题目是二维Hash，我们讲讲二维Hash，仍然是那个参数\(a\)，对于一个矩阵，，行的处理：\(P(i,j)=P(i,j-1)*a+v(i,j)\)，而列呢则是：\(P(i,1)=P(i-1,m)*a+v(i,1)\)，所以对于\(i\)行\(j\)列的数，它参数\(a\)的指数是\((n-i)*m+(m-j+1)\)。

注：代码中的模数直接采用unsigned long long 的自然溢出来处理。

那么如何在\(O(nm)\)的时间预处理并且在\(O(1)\)的时间内计算出子矩阵的Hash呢？

预处理我就不说了，但这个\(O(1)\)真的挺有意思的，我们不难发现，上下两行的指数差是\(m\)，左右列是\(1\)，我们可以利用这个性质像一维那样用容斥原理暴力搞，不过要分成四个部分罢了。

最后我们把母矩阵中所有大小为\(A*B\)的矩阵的Hash全部塞进数组里面，二分查找，此题完结。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define  N  1100
#define  M  1100000
using  namespace  std;
typedef  unsigned  long  long  LL;
int  a[N][N],b[N][N];
LL  ha[N][N],hb[N][N];
LL  pl=3,list[M],top,p[M];
int  n,m,A,B,Q;
char  st[N];
bool  check(LL  x)
{
	int  l=1,r=top,ans=0;
	while(l<=r)
	{
		int  mid=(l+r)/2;
		if(list[mid]<=x)ans=mid,l=mid+1;
		else  r=mid-1;
	}
	if(list[ans]==x)return  1;
	return  0;
}
int  main()
{
//	freopen("matrix4.in","r",stdin);
//	freopen("juruo.out","w",stdout); 
	scanf("%d%d%d%d",&n,&m,&A,&B);
	int  nm=n*m;
	p[0]=1;
	for(int  i=1;i<=nm;i++)
	{
		p[i]=p[i-1]*pl;
	}
	for(int  i=1;i<=n;i++)
	{
		scanf("%s",st+1);
		for(int  j=1;j<=m;j++)a[i][j]=st[j]-'0';
	}
	scanf("%d",&Q);
	for(int  i=1;i<=n;i++)
	{
		for(int  j=1;j<=m;j++)ha[i][j]=ha[i][j-1]*pl+a[i][j];
	}
	for(int  i=1;i<=n;i++)
	{
		for(int  j=1;j<=m;j++)
		{
			ha[i][j]=ha[i-1][j]*p[m]+ha[i][j];
			if(i>=A  &&  j>=B)
			{
				int  x=i-A,y=j-B;
				list[++top]=(ha[i][j]-ha[x][j]*p[A*m])-(ha[i][y]-ha[x][y]*p[A*m])*p[B];//计算子矩阵的Hash
			}
		}
	}
	sort(list+1,list+top+1);
	for(int  t=1;t<=Q;t++)
	{
		for(int  i=1;i<=A;i++)
		{
			scanf("%s",st+1);
			for(int  j=1;j<=B;j++)b[i][j]=st[j]-'0';
		}
		for(int  i=1;i<=A;i++)
		{
			for(int  j=1;j<=B;j++)hb[i][j]=hb[i][j-1]*pl+b[i][j];
		}
		for(int  i=1;i<=A;i++)
		{
			for(int  j=1;j<=B;j++)hb[i][j]=hb[i-1][j]*p[m]+hb[i][j];
		}
		printf("%d\n",check(hb[A][B]));
	}
	return  0;
}