【题目描述】
给定数字矩阵，求矩阵中 上下对称 且 左右对称 的 正方形子矩阵 的 个数。
【题目链接】
BZOJ 1414 对称的正方形 【ZJOI 2009】
【解题思路】
二维的回文串？
似乎正解是 Manacher，但我太弱啦没有看懂，所以就写了 HASH + 二分 的方法，卡一卡还是能过的。
先说一维的 HASH 做法吧，同 Manacher 一样，先在相邻的数之间加上某个没有出现过的数，以统一奇偶，然后预处理前缀哈希，预处理后缀哈希，我们可以 $O(1)$ 判断一个子串是不是回文的，只需要比较这个子串两个哈希的值就可以了。
然后我们枚举子串的中心点，然后二分长度，用哈希检验就可以了。
二分的依据就在于，对于同一个中心点，若某个长度的子串是回文的，那么长度比其短的一定是回文的，这很显然吧。
二维的情形是类似的，先在中间加数，然后预处理出以四个角为起点的哈希，比较四个哈希就可以判断。然后枚举正方形的中心点，二分边长，就解决了。
复杂度 $O(n^2\log n)$，常数较大。
【AC代码】
写起来略麻烦。
#include <cstdio>
#include <iostream>
#include <algorithm>
namespace IO{
const int IN_SIZE = 1 << 15;
char inBuf[IN_SIZE];
char *S, *T, ch;
inline char getchar(){
if(S == T) S = inBuf, T = inBuf + fread(inBuf, 1, IN_SIZE, stdin);
if(S == T) return EOF;
return *S++;
}
inline void readint(int &x){
do ch = getchar(); while(ch < '0' || ch > '9');
for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ '0');
}
}
const int MAXN = 1000;
const int MAXM = 1000;
const int REALN = 2 * MAXN + 1;
const int REALM = 2 * MAXM + 1;
typedef unsigned int HashInt;
const HashInt BASEX = 5261;
const HashInt BASEY = 1205;
HashInt powX[REALN + 1], powY[REALM + 1];
HashInt f[4][REALN + 1 + 1][REALN + 1 + 1];
int a[REALN + 1][REALM + 1];
int n, m;
inline void initHash(){
powX[0] = 1;
for(int i = 1; i <= n; i++) powX[i] = powX[i - 1] * BASEX;
powY[0] = 1;
for(int i = 1; i <= m; i++) powY[i] = powY[i - 1] * BASEY;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) f[0][i][j] = f[1][i][j] = f[2][i][j] = f[3][i][j] = a[i][j];
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) f[0][i][j] += f[0][i][j - 1] * BASEX;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) f[0][i][j] += f[0][i - 1][j] * BASEY;
for(int i = 1; i <= n; i++) for(int j = m; j >= 1; j--) f[1][i][j] += f[1][i][j + 1] * BASEX;
for(int i = 1; i <= n; i++) for(int j = m; j >= 1; j--) f[1][i][j] += f[1][i - 1][j] * BASEY;
for(int i = n; i >= 1; i--) for(int j = 1; j <= m; j++) f[2][i][j] += f[2][i][j - 1] * BASEX;
for(int i = n; i >= 1; i--) for(int j = 1; j <= m; j++) f[2][i][j] += f[2][i + 1][j] * BASEY;
for(int i = n; i >= 1; i--) for(int j = m; j >= 1; j--) f[3][i][j] += f[3][i][j + 1] * BASEX;
for(int i = n; i >= 1; i--) for(int j = m; j >= 1; j--) f[3][i][j] += f[3][i + 1][j] * BASEY;
}
inline HashInt hash(int x1, int y1, int x2, int y2, int d){
HashInt powX = ::powX[x2 - x1 + 1], powY = ::powY[y2 - y1 + 1];
if(d == 0){
return f[0][x2][y2] - f[0][x1 - 1][y2] * powY - f[0][x2][y1 - 1] * powX + f[0][x1 - 1][y1 - 1] * powX * powY;
} else if(d == 1){
return f[1][x2][y1] - f[1][x1 - 1][y1] * powY - f[1][x2][y2 + 1] * powX + f[1][x1 - 1][y2 + 1] * powX * powY;
} else if(d == 2){
return f[2][x1][y2] - f[2][x2 + 1][y2] * powY - f[2][x1][y1 - 1] * powX + f[2][x2 + 1][y1 - 1] * powX * powY;
} else if(d == 3){
return f[3][x1][y1] - f[3][x2 + 1][y1] * powY - f[3][x1][y2 + 1] * powX + f[3][x2 + 1][y2 + 1] * powX * powY;
} else{
throw;
}
}
inline bool check(int x1, int y1, int x2, int y2){
HashInt std = hash(x1, y1, x2, y2, 0);
return (
std == hash(x1, y1, x2, y2, 1) &&
std == hash(x1, y1, x2, y2, 2) &&
std == hash(x1, y1, x2, y2, 3)
);
}
inline int solve(int x, int y){
int l = 1, r = std::min(std::min(x, n - x + 1), std::min(y, m - y + 1)), ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(x - mid + 1, y - mid + 1, x + mid - 1, y + mid - 1)) ans = mid, l = mid + 1; else r = mid - 1;
}
return ans;
}
inline int solve(){
initHash();
int ans = 0;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if((i + j & 1) == 0){
ans += solve(i, j) >> 1;
}
return ans;
}
int main(){
IO::readint(n), IO::readint(m);
n = 2 * n + 1, m = 2 * m + 1;
for(int i = 2; i <= n; i += 2) for(int j = 2; j <= m; j += 2) IO::readint(a[i][j]);
printf("%d\n", solve());
return 0;
}
就是这样啦