對稱正方形【二維Hash】【二分】

>Link

ybtoj對稱正方形

>解題思路

本着“自己做出來”态度打了一次，不知道為什麼怎麼都a不了，檢查了好多遍都找不出bug，隻好看題解的思路打了🤕

枚舉每一個中心點，二分最多可以向四周擴散的長度，check目前擴散出的正方形是否合法

這裡要用到二維哈希來記錄每一個矩陣的狀态，求一個左上角是(x,y)右下角是(xx,yy)的矩陣哈希值與字首和的思想類似(?)

因為是求 對稱 正方形，是以一個矩陣肯定要分别左右鏡面、上下鏡面後都與原矩陣一樣，才算合法

這樣我們可以預處理出原矩陣、左右鏡面、上下鏡面的hash，二分時直接計算判斷就行了

>代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ull unsigned long long
#define N 1010
using namespace std;

const ull p1 = 1000000007, p2 = 1000000009;
int n, m, l, r, mid, ans, w;
ull a[N][N], b[N][N], c[N][N];
ull ha[N][N], hb[N][N], hc[N][N], l1[N], l2[N];

bool check (int ux, int uy, int uxx, int uyy)
{
	int x = ux, y = uy, xx = uxx, yy = uyy;
	ull r1 = ha[xx][yy] - ha[x - 1][yy] * l2[xx - x + 1]
	         - ha[xx][y - 1] * l1[yy - y + 1]
	         + ha[x - 1][y - 1] * l1[yy - y + 1] * l2[xx - x + 1];
	x = ux, y = m - uyy + 1, xx = uxx, yy = m - uy + 1; //鏡面後的矩陣位置不一樣
	ull r2 = hb[xx][yy] - hb[x - 1][yy] * l2[xx - x + 1]
	         - hb[xx][y - 1] * l1[yy - y + 1]
	         + hb[x - 1][y - 1] * l1[yy - y + 1] * l2[xx - x + 1];
	x = n - uxx + 1, y = uy, xx = n - ux + 1, yy = uyy;
	ull r3 = hc[xx][yy] - hc[x - 1][yy] * l2[xx - x + 1]
	         - hc[xx][y - 1] * l1[yy - y + 1]
	         + hc[x - 1][y - 1] * l1[yy - y + 1] * l2[xx - x + 1];
	if (r1 != r2 || r1 != r3) return 0;
	return 1;
}
void work (int x, int y)
{
	w = 0;
	l = 1, r = min (min (min (x - 1, n - x + 1), y - 1), m - y + 1);
	while (l <= r)
	{
		mid = (l + r) / 2;
		if (check (x - mid, y - mid, x + mid, y + mid))
		  l = mid + 1, w = max (w, mid);
		else r = mid - 1;
	} //以(x,y)為中心點
	ans += w;
	w = 0;
	l = 1, r = min (min (min (x, n - x), y), m - y);
	while (l <= r)
	{
		mid = (l + r) / 2;
		if (check (x - mid + 1, y - mid + 1, x + mid, y + mid))
		{
			l = mid + 1;
			w = max (w, mid);
		}
		else r = mid - 1;
	} //沒有中心點，即中心點不在格子上的情況。我這裡定義(x,y)在中心點的左上方
	ans += w;
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= m; j++) scanf ("%lld", &a[i][j]);
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= m; j++)
	  {
	  	b[i][j] = a[i][m - j + 1]; //左右
	  	c[i][j] = a[n - i + 1][j]; //上下
	  }
	l1[0] = l2[0] = 1;
	for (int i = 1; i <= max (n, m); i++)
	  l1[i] = l1[i - 1] * p1, l2[i] = l2[i - 1] * p2;
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= m; j++)
	  {
	  	ha[i][j] = ha[i][j - 1] * p1 + a[i][j];
	  	hb[i][j] = hb[i][j - 1] * p1 + b[i][j];
	  	hc[i][j] = hc[i][j - 1] * p1 + c[i][j];
	  }
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= m; j++)
	  {
	  	ha[i][j] += ha[i - 1][j] * p2;
	  	hb[i][j] += hb[i - 1][j] * p2;
	  	hc[i][j] += hc[i - 1][j] * p2;
	  }
		
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= m; j++)
	    work (i, j);
	printf ("%d", ans + n * m);
	return 0;
}