「ZJOI2009」对称的正方形 - 单调队列+二维Manacher / 二分+Hash

题目大意

    求一个矩阵中回文正方形的个数。
    回文正方形即指沿着中轴左右对称、上下对称。

---

题目分析

这道题可以用单调队列+二维Manacher来搞。
然而显然代码量高，调试复杂，我们不妨使用第二种解法。
没错我就是要用非确定性算法！

我们设置一下从左上角开始的Hash函数：

$$\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}k1^{x}\cdot k2^{y}\cdot a[i][j]$$

不难发现这个Hash函数是二维的前缀和形式，可以提取出一个子矩阵的Hash值。
再计算一下右上角开始的Hash与左下角开始的Hash，即可比较是否两个方向对称了。

为了不特判偶数情况，我们每隔一行一列插入一个空行，将偶数情况转化为奇数情况。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=2005,base1=123,base2=10007; 

int n,m,a[maxn][maxn],ans=0;
unsigned int LU[maxn][maxn],RU[maxn][maxn],LD[maxn][maxn],Pow1[maxn],Pow2[maxn];

bool Check(int x1,int y1,int x2,int y2) {
	int h1=LU[x2][y2]-LU[x2][y1-1]*Pow2[y2-y1+1]-LU[x1-1][y2]*Pow1[x2-x1+1]+LU[x1-1][y1-1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
	int h2=RU[x2][y1]-RU[x2][y2+1]*Pow2[y2-y1+1]-RU[x1-1][y1]*Pow1[x2-x1+1]+RU[x1-1][y2+1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
	if(h1!=h2)return false;
	int h3=LD[x1][y2]-LD[x1][y1-1]*Pow2[y2-y1+1]-LD[x2+1][y2]*Pow1[x2-x1+1]+LD[x2+1][y1-1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
	return h2==h3;
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			a[(i<<1)-1][(j<<1)-1]=Get_Int();
	n=(n<<1)-1,m=(m<<1)-1;
	Pow1[0]=Pow2[0]=1;
	for(int i=1; i<=n; i++)Pow1[i]=Pow1[i-1]*base1;
	for(int i=1; i<=m; i++)Pow2[i]=Pow2[i-1]*base2;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)LU[i][j]=LU[i][j-1]*base2+a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)LU[i][j]+=LU[i-1][j]*base1;
	for(int i=1; i<=n; i++)
		for(int j=m; j>=1; j--)RU[i][j]=RU[i][j+1]*base2+a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=m; j>=1; j--)RU[i][j]+=RU[i-1][j]*base1;
	for(int i=n; i>=1; i--)
		for(int j=1; j<=m; j++)LD[i][j]=LD[i][j-1]*base2+a[i][j];
	for(int i=n; i>=1; i--)
		for(int j=1; j<=m; j++)LD[i][j]+=LD[i+1][j]*base1;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(!((i+j)&1)) {
				int Left=1,Right=min({i,j,n-i+1,m-j+1});
				while(Left<=Right) {
					int mid=(Left+Right)>>1;
					if(Check(i-mid+1,j-mid+1,i+mid-1,j+mid-1))Left=mid+1;
					else Right=mid-1;
				}
				ans+=(Right+(i&1))>>1;
			}
	printf("%d\n",ans);
	return 0;
}