ZJOI2009 对称的正方形

P2601 [ZJOI2009] 对称的正方形

题目大意

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

$1\le n,m\le 1000$

题解

首先，我们对原矩阵、左右翻转后的矩阵、上下翻转后的矩阵分别做二维哈希的处理。

对于边长为偶数的正方形，枚举正方形中心的格点并二分最远的符合题意的长度。

对于边长为奇数的正方形，枚举正方形中心的各自并二分最远的符合题意的长度。

判断是否符合题意可以通过判断三个矩阵中对应位置的二维哈希值是否相等来得到。

最后记得加上单个格子的贡献。

时间复杂度为$O(nm\log \min (n,m))$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
const int bs1=131,bs2=233;
const long long mod=1e9+7;
int n,m,a[N+5][N+5],b[N+5][N+5],c[N+5][N+5];
long long ans=0,f1[N+5],f2[N+5];
long long s1[N+5][N+5],s2[N+5][N+5],s3[N+5][N+5];
long long gt1(int ux,int uy,int dx,int dy){
	return s1[dx][dy]-s1[dx][uy-1]*f1[dy-uy+1]%mod-s1[ux-1][dy]*f2[dx-ux+1]%mod+s1[ux-1][uy-1]*f1[dy-uy+1]%mod*f2[dx-ux+1]%mod;
}
long long gt2(int ux,int uy,int dx,int dy){
	return s2[dx][dy]-s2[dx][uy-1]*f1[dy-uy+1]%mod-s2[ux-1][dy]*f2[dx-ux+1]%mod+s2[ux-1][uy-1]*f1[dy-uy+1]%mod*f2[dx-ux+1]%mod;
}
long long gt3(int ux,int uy,int dx,int dy){
	return s3[dx][dy]-s3[dx][uy-1]*f1[dy-uy+1]%mod-s3[ux-1][dy]*f2[dx-ux+1]%mod+s3[ux-1][uy-1]*f1[dy-uy+1]%mod*f2[dx-ux+1]%mod;
}
bool check(int ux,int uy,int dx,int dy){
	if(ux<1||uy<1||dx>n||dy>m) return 0;
	long long v1,v2,v3;
	v1=(gt1(ux,uy,dx,dy)%mod+mod)%mod;
	v2=(gt2(n-dx+1,uy,n-ux+1,dy)%mod+mod)%mod;
	v3=(gt3(ux,m-dy+1,dx,m-uy+1)%mod+mod)%mod;
	return v1==v2&&v2==v3;
}
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]);
			b[n-i+1][j]=a[i][j];
			c[i][m-j+1]=a[i][j];
		}
	}
	f1[0]=f2[0]=1;
	for(int i=1;i<=min(n,m);i++){
		f1[i]=f1[i-1]*bs1%mod;
		f2[i]=f2[i-1]*bs2%mod;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s1[i][j]=(s1[i][j-1]*bs1+a[i][j])%mod;
			s2[i][j]=(s2[i][j-1]*bs1+b[i][j])%mod;
			s3[i][j]=(s3[i][j-1]*bs1+c[i][j])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s1[i][j]=(s1[i-1][j]*bs2+s1[i][j])%mod;
			s2[i][j]=(s2[i-1][j]*bs2+s2[i][j])%mod;
			s3[i][j]=(s3[i-1][j]*bs2+s3[i][j])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int l=1,r=n,mid;
			while(l<=r){
				mid=l+r>>1;
				if(check(i-mid+1,j-mid+1,i+mid,j+mid)) l=mid+1;
				else r=mid-1;
			}
			ans+=l-1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int l=1,r=n,mid;
			while(l<=r){
				mid=l+r>>1;
				if(check(i-mid,j-mid,i+mid,j+mid)) l=mid+1;
				else r=mid-1;
			}
			ans+=l-1;
		}
	}
	ans+=n*m;
	printf("%lld",ans);
	return 0;
}