题解:枚举中点,然后二分+hash即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1010;
typedef unsigned long long ull;
typedef long long ll;
int v[maxn][maxn];
int n,m;
ll ans;
ull h1[maxn][maxn],h2[maxn][maxn],h3[maxn][maxn],h4[maxn][maxn],b1[maxn],b2[maxn];
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}
	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();
	return ret*f;
}
int main()
{
	n=rd(),m=rd();
	int i,j,l,r,mid;
	ull g1,g2,g3,g4;
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	v[i][j]=rd();
	for(b1[0]=b2[0]=1,i=1;i<=n;i++)	b1[i]=b1[i-1]*233,b2[i]=b2[i-1]*2333;
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	h1[i][j]=h1[i-1][j]*233+h1[i][j-1]*2333-h1[i-1][j-1]*233*2333+v[i][j];
	for(i=1;i<=n;i++)	for(j=m;j>=1;j--)	h2[i][j]=h2[i-1][j]*233+h2[i][j+1]*2333-h2[i-1][j+1]*233*2333+v[i][j];
	for(i=n;i>=1;i--)	for(j=1;j<=m;j++)	h3[i][j]=h3[i+1][j]*233+h3[i][j-1]*2333-h3[i+1][j-1]*233*2333+v[i][j];
	for(i=n;i>=1;i--)	for(j=m;j>=1;j--)	h4[i][j]=h4[i+1][j]*233+h4[i][j+1]*2333-h4[i+1][j+1]*233*2333+v[i][j];
	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)
	{
		l=1,r=min(min(i,j),min(n-i+1,m-j+1))+1;
		while(l<r)
		{
			mid=l+r>>1;
			g1=h1[i][j]-h1[i-mid][j]*b1[mid]-h1[i][j-mid]*b2[mid]+h1[i-mid][j-mid]*b1[mid]*b2[mid];
			g2=h2[i][j]-h2[i-mid][j]*b1[mid]-h2[i][j+mid]*b2[mid]+h2[i-mid][j+mid]*b1[mid]*b2[mid];
			g3=h3[i][j]-h3[i+mid][j]*b1[mid]-h3[i][j-mid]*b2[mid]+h3[i+mid][j-mid]*b1[mid]*b2[mid];
			g4=h4[i][j]-h4[i+mid][j]*b1[mid]-h4[i][j+mid]*b2[mid]+h4[i+mid][j+mid]*b1[mid]*b2[mid];
			if(g1==g2&&g1==g3&&g1==g4)	l=mid+1;
			else	r=mid;
		}
		ans+=l-1;
		l=1,r=min(min(i,j),min(n-i,m-j))+1;
		while(l<r)
		{
			mid=l+r>>1;
					g1=h1[i][j]-h1[i-mid][j]*b1[mid]-h1[i][j-mid]*b2[mid]+h1[i-mid][j-mid]*b1[mid]*b2[mid];
				j++,g2=h2[i][j]-h2[i-mid][j]*b1[mid]-h2[i][j+mid]*b2[mid]+h2[i-mid][j+mid]*b1[mid]*b2[mid];
			i++,j--,g3=h3[i][j]-h3[i+mid][j]*b1[mid]-h3[i][j-mid]*b2[mid]+h3[i+mid][j-mid]*b1[mid]*b2[mid];
				j++,g4=h4[i][j]-h4[i+mid][j]*b1[mid]-h4[i][j+mid]*b2[mid]+h4[i+mid][j+mid]*b1[mid]*b2[mid];
			i--,j--;
			if(g1==g2&&g1==g3&&g1==g4)	l=mid+1;
			else	r=mid;
		}
		ans+=l-1;
	}
	printf("%lld",ans);
	return 0;
}
【BZOJ1414/3705】[ZJOI2009]对称的正方形 二分+hash
原文:http://www.cnblogs.com/CQzhangyu/p/7366987.html