链接：
题目大意：
在一个 (n imes m) 的矩阵内求出上下左右都对称的正方形。
(1leq n,mleq 1000)。
正文：
对于本题有一个性质：一个合法的正方形内部也是合法的正方形。
然后可以得到一个暴力的思路。对于每一个点往外扩张，每次判合法就可以只判断最外一层，这是边长为奇；还要预处理出所有边长为二的合法正方形，同样向外扩张。
每次判外圈时，相当于有若干个长方形要在合法的位置：
如图，不同颜色的格子可以看作不同长方形的顶点。
一般一道题想得这么复杂，要换个思路，重新审题。
其实判合法并不用这么麻烦。既然合法的正方形是上下、左右对称，那我们就取正方形的左上部分、左右颠倒的右上部分、上下颠倒的左下部分判是否一样。
可以通过二维哈希判。
(mathcal{O}(n)) 往外扩张会超时，可以二分解决。这里最好不要像上文提到的枚举正方形的中心点，最好是枚举正方形的左上角，然后二分正方形的边长。
代码：
int n, m;
unsigned ll base1 = 87, base2 = 31;
unsigned ll a[N][N], b[N][N], c[N][N], ans;
unsigned ll Ha[N][N], Hb[N][N], Hc[N][N];
unsigned ll fac1[N], fac2[N];
bool check(int len, int x, int y)
{
if (x > n || y > m || x < len || y < len) return 0;
unsigned ll CHa = 0, CHb = 0, CHc = 0;
CHa = Ha[x][y] - Ha[x - len][y] * fac2[len] -
Ha[x][y - len] * fac1[len] + Ha[x - len][y - len] * fac1[len] * fac2[len];
int t = y; y = m - (y - len);
CHb = Hb[x][y] - Hb[x - len][y] * fac2[len] -
Hb[x][y - len] * fac1[len] + Hb[x - len][y - len] * fac1[len] * fac2[len];
y = t, x = n - (x - len);
CHc = Hc[x][y] - Hc[x - len][y] * fac2[len] -
Hc[x][y - len] * fac1[len] + Hc[x - len][y - len] * fac1[len] * fac2[len];
return CHa == CHb && CHb == CHc;
}
ll Binary(int i, int j, int f = 0)
{
int l = 0, r = min(i, j) + f, mid, tmp = f;
while (l <= r)
{
mid = l + r >> 1;
if (check(mid * 2 - f, i + mid, j + mid))
l = mid + 1, tmp = mid * 2 - f;
else r = mid - 1;
}
return (tmp + 1) / 2;
}
int main()
{
n = READ(), m = READ();
fac1[0] = fac2[0] = 1ull;
for (int i = 1; i <= n; i++)
fac1[i] = fac1[i - 1] * base1;
for (int i = 1; i <= m; i++)
fac2[i] = fac2[i - 1] * base2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
b[i][m - j + 1] = c[n - i + 1][j] = a[i][j] = READ();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
Ha[i][j] += Ha[i][j - 1] * base1 + a[i][j],
Hb[i][j] += Hb[i][j - 1] * base1 + b[i][j],
Hc[i][j] += Hc[i][j - 1] * base1 + c[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
Ha[i][j] += Ha[i - 1][j] * base2,
Hb[i][j] += Hb[i - 1][j] * base2,
Hc[i][j] += Hc[i - 1][j] * base2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
ans += Binary(i, j, 1) + Binary(i, j);
}
printf ("%llu
", ans);
return 0;
}