Description
Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。
Input
文件的第一行为两个整数n和m。接下来n行每行包含m个正整数，表示Orez得到的矩阵。
Output
文件中仅包含一个整数answer，表示矩阵中有answer个上下左右对称的正方形子矩阵。
hash+二分确定每个中心的最大对称正方形
#include<cstdio>
char buf[],*ptr=buf;
int _(){
int x=;
while(*ptr<)++ptr;
while(*ptr>)x=x*+*ptr++-;
return x;
}
typedef unsigned int u32;
int n,m;
int a[][];
u32 f[][][],pp1[],pp2[];
long long ans=;
const u32 p1=,p2=;
#define F(i,n) for(int i=1;i<=n;++i)
#define Fd(i,n) for(int i=n;i>=1;--i)
int min(int a,int b){return a<b?a:b;}
bool chk(int l1,int r1,int l2,int r2){
u32 v1=pp1[r1-l1+];
u32 v2=pp2[r1-l1+];
u32 h0=f[][r1][r2]-f[][r1][l2-]*v2-(f[][l1-][r2]-f[][l1-][l2-]*v2)*v1;
u32 h1=f[][r1][l2]-f[][r1][r2+]*v2-(f[][l1-][l2]-f[][l1-][r2+]*v2)*v1;
if(h0!=h1)return ;
u32 h2=f[][l1][r2]-f[][l1][l2-]*v2-(f[][r1+][r2]-f[][r1+][l2-]*v2)*v1;
return h0==h2;
}
int main(){
fread(buf,,sizeof(buf),stdin);
n=_(),m=_();
F(i,n)F(j,m)f[][i][j]=f[][i][j]=f[][i][j]=a[i][j]=_();
F(i,n){
F(j,m)f[][i][j]+=f[][i][j-]*p2;
F(j,m)f[][i][j]+=f[][i-][j]*p1;
}
F(i,n){
Fd(j,m)f[][i][j]+=f[][i][j+]*p2;
Fd(j,m)f[][i][j]+=f[][i-][j]*p1;
}
Fd(i,n){
F(j,m)f[][i][j]+=f[][i][j-]*p2;
F(j,m)f[][i][j]+=f[][i+][j]*p1;
}
pp1[]=pp2[]=;
F(i,n)pp1[i]=pp1[i-]*p1;
F(i,m)pp2[i]=pp2[i-]*p2; F(i,n)F(j,m){
int L=,R=min(min(i-,n-i),min(j-,m-j)),M=;
while(L<R){
if(chk(i-M,i+M,j-M,j+M))L=M;
else R=M-;
M=L+R+>>;
}
ans+=L+;
}
F(i,n-)F(j,m-)if(a[i][j]==a[i][j+]&&a[i][j]==a[i+][j]&&a[i][j]==a[i+][j+]){
int L=,R=min(min(i-,n--i),min(j-,m--j)),M=;
while(L<R){
if(chk(i-M,i+M+,j-M,j+M+))L=M;
else R=M-;
M=L+R+>>;
}
ans+=L+;
}
printf("%lld\n",ans);
return ;
}