本文共 1871 字，大约阅读时间需要 6 分钟。

题目大意

给出一个 $n\times m$ 的矩阵，求矩阵中上下左右对称的正方形子矩阵的个数。

思路

首先这道题暴力去搞肯定会超时，

大体思路解决后，思考怎样发散。

判断部分就是把构造出的三个哈希矩阵直接对比(当然是数值的比较)，这里不再赘述。

二分要分奇偶，因为奇数和偶数有统计上的差异。

代码

#include
   
    #include
    
     #include
     
      using namespace std;unsigned long long a[1010][1010],b[1010][1010],c[1010][1010];unsigned long long f1[1000010],f2[1000010];int n,m,ans;bool check(int mid,int i,int j){   	if(i-mid<0||j-mid<0||i>n||j>m||i<0)	  return 0;	int a1=a[i][j]-a[i-mid][j]*f2[mid]-a[i][j-mid]*f1[mid]+a[i-mid][j-mid]*f1[mid]*f2[mid];	int bx=n-(i-mid),by=m-(j-mid);	int b1=b[bx][j]-b[bx-mid][j]*f2[mid]-b[bx][j-mid]*f1[mid]+b[bx-mid][j-mid]*f1[mid]*f2[mid];	int c1=c[i][by]-c[i-mid][by]*f2[mid]-c[i][by-mid]*f1[mid]+c[i-mid][by-mid]*f1[mid]*f2[mid];	//cout<
      
       <<" "<
       
        <<" "<
        
         <
         
          >n>>m; f1[0]=1ull,f2[0]=1ull; for(int i=1; i<=max(n,m); i++) f1[i]=f1[i-1]*1000000009ull,f2[i]=f2[i-1]*1000000007ull; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { scanf("%ulld",&a[i][j]); c[i][m-j+1]=a[i][j]; //左右颠倒 b[n-i+1][j]=a[i][j]; //上下颠倒 //（不明白的手推一下） } yhash(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { int l=0,r=min(i,j)+1,mid=0,maxx=1; while(l<=r)//奇数 { mid=(l+r)/2; if(check(mid*2-1,i+mid,j+mid)) //扩大到以中心点为中心 l=mid+1,maxx=max(mid*2-1,maxx); else r=mid-1; } ans=ans+(maxx+1)/2; maxx=0; l=0,r=min(i,j); while(l<=r) //偶数 { mid=(l+r)/2; if(check(mid*2,i+mid,j+mid)) //同上 l=mid+1,maxx=max(mid*2,maxx); else r=mid-1; } ans=ans+(maxx+1)/2; } cout<