【字符矩阵哈希】【二分答案】【哈希表】bzoj1567 [JSOI2008]Blue Mary的战役地图

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define MOD 2501
typedef unsigned long long ull;
const ull seed1=3659,seed2=1789;
ull sum[51][51],sum2[51][51],v[MOD],pow1[51],pow2[51];
int n,ans,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++;
}
bool check(const int &x)
{
	memset(first,-1,sizeof(first)); en=0;
	for(int i=x;i<=n;i++)
	  for(int j=x;j<=n;j++)
	    Insert(sum[i][j]
		-sum[i-x][j]*pow1[x]
		-sum[i][j-x]*pow2[x]
		+sum[i-x][j-x]*pow1[x]*pow2[x]);
	for(int i=x;i<=n;i++)
	  for(int j=x;j<=n;j++)
	    {
	      ull t=sum2[i][j]
		  -sum2[i-x][j]*pow1[x]
		  -sum2[i][j-x]*pow2[x]
		  +sum2[i-x][j-x]*pow1[x]*pow2[x];
		  int o=(int)(t%MOD);
		  for(int i=first[o];i!=-1;i=next[i])
		    if(t==v[i])
		      return 1;
	    }
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  cin>>sum[i][j];
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  cin>>sum2[i][j];
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  sum[i][j]+=sum[i-1][j]*seed1;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  sum[i][j]+=sum[i][j-1]*seed2;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  sum2[i][j]+=sum2[i-1][j]*seed1;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	  sum2[i][j]+=sum2[i][j-1]*seed2;
	pow1[0]=pow2[0]=1;
    for(int i=1;i<=n;i++)
	  pow1[i]=pow1[i-1]*seed1,
	  pow2[i]=pow2[i-1]*seed2;
	int l=1,r=n;
	while(l<=r)
	  {
		int mid=l+r>>1;
		if(check(mid))
		  ans=mid,l=mid+1;
		else r=mid-1;
	  }
	printf("%d\n",ans);
	return 0;
}