Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。

由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。

具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

Solution

这题的数据范围是允许我们n^4log(n)做的，大概就是二分一个答案，暴力枚举两个矩形的左上角。

但我们必须做到O(1)查询，所以需要预处理。

我们先设g[i][j][k]表示从第i行第j列，从这个格子往后K个格子的哈希值。

在用一个f[i][j][k]表示以i，j开头的边长为k的正方形的哈希值。

实现的话看代码就好了。

Code

#include
     
      #include
      
       #define N 52using namespace std;typedef unsigned long long ll;int n,ans;ll HA[N][N][N],HB[N][N][N],ha[N][N][N],hb[N][N][N],a[N][N],b[N][N]; const ll base=233;ll power(ll x,ll y){    ll ans=1;    while(y){        if(y&1)ans*=x;        x*=x;        y>>=1;    }    return ans;}inline bool check(int pos){    for(int i=1;i<=n-pos+1;++i)      for(int j=1;j<=n-pos+1;++j)        for(int k=1;k<=n-pos+1;++k)          for(int l=1;l<=n-pos+1;++l)            if(HA[i][j][pos]==HB[k][l][pos])return true;    return false;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%ull",&a[i][j]);    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%ull",&b[i][j]);    for(int k=1;k<=n;++k)      for(int i=1;i<=n;++i)        for(int j=1;j<=n-k+1;++j){            ha[i][j][k]=a[i][j];hb[i][j][k]=b[i][j];            for(int l=j+1;l
       
        >1;        if(check(mid)){            ans=mid;            l=mid+1;        }        else r=mid-1;    }    cout<