【BZOJ1414】[ZJOI2009]对称的正方形（哈希）

题面

BZOJ

洛谷

题解

深思熟虑一波，发现一个矩阵如果左右对称的话，那么它每行都是一个回文串，同理，如果上下对称的话，那么每列都是一个回文串。既然每行每列都是一个回文串，那么我们把它中心对称一下它还是一个回文串，妙蛙。

我们在矩阵中间补上\(0\)，这样子就有回文中心了，对于每一个中心算算它往左右能够拓展的最大回文串的长度，然后二分计算一下能够得到的最大矩阵就好了。

至于哈希什么的，自己随便ＹＹ一下吧，我自己写半天不会，直接照着别人的写了一遍额。。

#include<iostream>

#include<cstdio>

using namespace std;

#define uint unsigned int

#define MAX 2020

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

const uint base1=19260817,base2=233;

int n,m,g[MAX][MAX],ans,tot;

uint pw1[MAX*MAX],pw2[MAX*MAX],s[3][MAX][MAX];

bool check(int l1,int r1,int l2,int r2)

{

	int len1=r1-l1+1,len2=r2-l2+1;

	int s0=s[0][r1][r2]-s[0][r1][l2-1]*pw2[len2]-s[0][l1-1][r2]*pw1[len1]+s[0][l1-1][l2-1]*pw1[len1]*pw2[len2];

	int s1=s[1][r1][l2]-s[1][r1][r2+1]*pw2[len2]-s[1][l1-1][l2]*pw1[len1]+s[1][l1-1][r2+1]*pw1[len1]*pw2[len2];

	int s2=s[2][l1][r2]-s[2][l1][l2-1]*pw2[len2]-s[2][r1+1][r2]*pw1[len1]+s[2][r1+1][l2-1]*pw1[len1]*pw2[len2];

	if(s0!=s1||s0!=s2||s1!=s2)return false;

	return true;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			g[i*2-1][j*2-1]=read();

	n=n*2-1,m=m*2-1;tot=n*m;pw1[0]=pw2[0]=1;

	for(int i=1;i<=tot;++i)pw1[i]=pw1[i-1]*base1;

	for(int i=1;i<=tot;++i)pw2[i]=pw2[i-1]*base2;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			s[0][i][j]=s[0][i][j-1]*base2+g[i][j];

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			s[0][i][j]+=s[0][i-1][j]*base1;

	for(int i=1;i<=n;++i)

		for(int j=m;j;--j)

			s[1][i][j]=s[1][i][j+1]*base2+g[i][j];

	for(int i=1;i<=n;++i)

		for(int j=m;j;--j)

			s[1][i][j]+=s[1][i-1][j]*base1;

	for(int i=n;i;--i)

		for(int j=1;j<=m;++j)

			s[2][i][j]=s[2][i][j-1]*base2+g[i][j];

	for(int i=n;i;--i)

		for(int j=1;j<=m;++j)

			s[2][i][j]+=s[2][i+1][j]*base1;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(!((i+j)&1))

			{

				int l=1,r=min(min(i,n-i+1),min(j,m-j+1)),ret=0;

				while(l<=r)

				{

					int mid=(l+r)>>1;

					if(check(i-mid+1,i+mid-1,j-mid+1,j+mid-1))ret=mid,l=mid+1;

					else r=mid-1;

				}

				ans+=(ret+(i&1))>>1;

			}

	printf("%d\n",ans);

	return 0;

}