分析

根据对称的定义，显然满足单调性。再看看范围，容易想到二分答案。

如何判断一个正方形是对称正方形？可以用二维 Hash 解决。

以下分为二分和二维 Hash 两个部分展开。

二分部分

首先确定，二分成立需要单调性，所以一定是从中心点二分，但是当正方形为奇数的时候中心点在中央的格子，那么偶数呢？

实际上，边长为偶数的时候正方形的重心在一个格点（就是一个点，不是格子）。

概括一下：

• 对于长度为奇数的正方形，以格子（一个 1 \times 1 的正方形）为中心二分最远符合条件的长度。

• 对于长度为偶数的正方形，以格点（就是一个点）为中心二分最远符合条件的长度 那么二分的 check 函数就可以用二维 Hash 来 O(1) 判断。

二维 Hash 部分

简单讲解一下板子需要注意的地方。

二维 Hash 的作用就是判断矩阵是否相同。

具体实现上就是横向和纵向分别算两次 Hash 值（base1 , base2 取不同的值，模数 mod 取一个值)。

对于 Hash 值的查询，类似二维前缀和，下面贴的代码中 mi1 , base1 对应纵坐标 y ， mi2 , base2 对应横坐标 x，记住这个对应关系基本就不会写错。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
const int INF = 0x3f3f3f3f,N = 1e3+10,base1 = 233,base2 = 133;
const ll mod = 1e9+9; 
ull mi1[N<<1],mi2[N<<1],sum[N<<1][N<<1];
int len,a[N<<1][N<<1],n,m;
int ans;
void init()
{
    mi1[0]=mi2[0]=1;
    //这里所有的n,m不要忘记×2 
    for(int i=1;i<=m<<1;i++) mi1[i]=(mi1[i-1]*base1);
    for(int i=1;i<=n<<1;i++) mi2[i]=(mi2[i-1]*base2);
    for(int i=1;i<=n<<1;i++)
        for(int j=1;j<=m<<1;j++)     
            sum[i][j]=sum[i][j-1]*base1+a[i][j];
    for(int i=1;i<=n<<1;i++)
        for(int j=1;j<=m<<1;j++)     
            sum[i][j]+=sum[i-1][j]*base2;//注意这里是+= 
}
inline ll Hash(int xa,int ya,int xb,int yb)
{
    return sum[xb][yb]-sum[xa-1][yb]*mi2[xb-xa+1]-
           sum[xb][ya-1]*mi1[yb-ya+1]+
           sum[xa-1][ya-1]*mi1[yb-ya+1]*mi2[xb-xa+1];
}
inline bool check(int xa,int ya,int xb,int yb)
{
    return Hash(xa,ya,xb,yb)==Hash((n<<1)-xb+1,ya,(n<<1)-xa+1,yb)&&
           Hash(xa,ya,xb,yb)==Hash(xa,(m<<1)-yb+1,xb,(m<<1)-ya+1);//+1要想好 
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);           
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            a[i+n][j]=a[n-i+1][j];
            a[i][j+m]=a[i][m-j+1]; 
        }
    init();//忘记调用init()还调了半天 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            //对于长度为奇数的正方形，以格子（一个1*1的正方形）为中心二分最远符合条件的长度
            int l=0,r=max(n,m);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(i-mid>=1&&j-mid>=1&&i+mid<=n&&j+mid<=m&&check(i-mid,j-mid,i+mid,j+mid)) l=mid;
                else r=mid-1;
            }
            ans+=l+1;
            //对于长度为偶数的正方形，以格点（就是一个点）为中心二分最远符合条件的长度
            l=0,r=max(n,m);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(i-mid+1>=1&&j-mid+1>=1&&i+mid<=n&&j+mid<=m&&check(i-mid+1,j-mid+1,i+mid,j+mid)) l=mid;
                else r=mid-1;
            }
            ans+=l;

        }
    printf("%d\n",ans); 
    return 0;
}