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

题目

思路

通过3次二维hash来判断是否有贡献，二分矩阵半径计算贡献，注意奇偶性问题，可以通过2次二分，也可以通过类似马拉车的方式解决（好学生打死不拉车）

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int a[1001][1001],b[1001][1001],c[1001][1001];int n,m;unsigned long long ha[1001][1001],hb[1001][1001],hc[1001][1001],p[1001],p2[1001],ans;bool check(int x,int y,int l){   	if (x>n||y>m||x
       
        
         >n>>m; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin>>a[i][j]; c[i][m-j+1]=a[i][j]; b[n-i+1][j]=a[i][j]; } } p2[0]=p[0]=1; for (int i=1;i<=1000;i++) p[i]=97*p[i-1],p2[i]=13331*p2[i-1]; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { ha[i][j]=ha[i][j-1]*97+a[i][j]; hb[i][j]=hb[i][j-1]*97+b[i][j]; hc[i][j]=hc[i][j-1]*97+c[i][j]; } } for (int i=2;i<=n;i++) { for (int j=1;j<=m;j++) { ha[i][j]=ha[i-1][j]*13331+ha[i][j]; hb[i][j]=hb[i-1][j]*13331+hb[i][j]; hc[i][j]=hc[i-1][j]*13331+hc[i][j]; } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { int l=1,r=n+m,mn=0; while (l<=r) { int mid=(l+r)>>1; if (check(i+mid,j+mid,mid*2+1)) l=mid+1,mn=max(mn,mid); else r=mid-1; } ans+=mn; l=1,r=n+m,mn=0; while (l<=r) { int mid=(l+r)>>1; if (check(i+mid,j+mid,mid*2)) l=mid+1,mn=max(mn,mid); else r=mid-1; } ans+=mn; } } cout<