题目大意
找到所有的上下左右都相同的正方形。
思路：二分 + 二维 Hash
这道题我们首先想到不能暴力判断一个正方形是否合法。
然后我们发现当一个正方形合法时，以这个正方形为中心且比它小的正方形也合法。
所以我们可以枚举每个正方形的中心点，二分求出以这个点为中心点的最大合法正方形的边长 $L$，其贡献是 $frac{L+1}{2}$
我们再回过来讨论如何判断一个正方形是否合法。
如果这个正方形的原来的、上下翻转的和左右翻转的矩阵都一样，那么这个正方形就是合法的。
以这个思路为出发点，我们可以用二维 Hash 预处理出这个正方形原来的、上下翻转的、左右反转的矩阵，每次判断的时候只要判断这三个矩阵是否相同就可以了。
在枚举中心点的时候要分类讨论奇偶情况，具体见代码。
二维 Hash 的求法：
先处理行，在处理列，查询和二维前缀和基本相似，但要注意二维 Hash 的加减有所不同。
代码
#include <cstdio>
#include <iostream>
#define RI register int
#define mid (l + r >> 1)
using namespace std;
template <class T>
inline void read(T &x) {
x = 0;
T f = 1;
char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -f;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
x *= f;
}
typedef unsigned long long ull;
const int N = 1e3 + 1;
const int B1 = 233;
const int B2 = 332;
int n, m, ans;
ull a[N][N], b[N][N], c[N][N];
ull pow1[N], pow2[N];
inline void Read() {
read(n), read(m);
for (RI i = 1; i <= n; i++)
for (RI j = 1; j <= m; j++)
read(a[i][j]),
b[i][m - j + 1] = a[i][j], //左右翻转
c[n - i + 1][j] = a[i][j]; //上下翻转
}
//二维哈希预处理
inline void init() {
for (RI i = 1; i <= n; i++)
for (RI j = 1; j <= m; j++)
a[i][j] += a[i][j - 1] * B1, b[i][j] += b[i][j - 1] * B1,
c[i][j] += c[i][j - 1] * B1;
for (RI i = 1; i <= n; i++)
for (RI j = 1; j <= m; j++)
a[i][j] += a[i - 1][j] * B2, b[i][j] += b[i - 1][j] * B2,
c[i][j] += c[i - 1][j] * B2;
pow1[0] = pow2[0] = 1;
for (RI i = 1, tmp = max(n, m); i <= tmp; i++)
pow1[i] = pow1[i - 1] * B1, pow2[i] = pow2[i - 1] * B2;
}
//判断三个矩阵是否相同
inline bool check(int x, int y, int le) {
//因为会自然溢出的缘故，unsigned 没有小于0的时候 所以不能写x-le<0 （细节
if (x > n || y > m || x < le || y < le) return false;
ull res1 = a[x][y] - a[x][y - le] * pow1[le] - a[x - le][y] * pow2[le] +
a[x - le][y - le] * pow1[le] * pow2[le];
int tmp = y;
y = m - (y - le); //位置要调整（细节
ull res2 = b[x][y] - b[x][y - le] * pow1[le] - b[x - le][y] * pow2[le] +
b[x - le][y - le] * pow1[le] * pow2[le];
y = tmp, x = n - (x - le); //位置要调整（细节
ull res3 = c[x][y] - c[x][y - le] * pow1[le] - c[x - le][y] * pow2[le] +
c[x - le][y - le] * pow1[le] * pow2[le];
return res1 == res2 && res2 == res3;
}
inline void solve() {
int tmp = min(n, m);
//这里要分两点讨论，边长为偶数的是枚举格点，而边长为奇数的则是枚举格子（细节
for (RI i = 0; i < n; i++)
for (RI j = 0; j < m; j++) {
int l = 1, r = tmp, res = 0;
while (l < r) {
if (check(i + mid, j + mid, mid + mid))
res = mid, l = mid + 1;
else
r = mid;
}
ans += res;
}
for (RI i = 0; i < n; i++)
for (RI j = 0; j < m; j++) {
int l = 1, r = tmp, res = 0;
while (l < r) {
if (check(i + mid, j + mid, mid + mid + 1))
res = mid, l = mid + 1;
else
r = mid;
}
ans += res;
}
ans += n * m; // 1格的也算对称正方形，不要漏了（细节
printf("%d
", ans);
}
int main() {
Read();
init();
solve();
return 0;
}