题目传送门(BZOJ)
题解 :
显然且麻烦的一个二维矩阵哈希
对于矩阵对称的处理就像对于回文的处理一样即可.
但是要维护四个哈希 : 左上/右上/左下/右下 的哈希
注意行和列要用不同的BASE,
然后O(NM)枚举中点, 分奇偶二分出当前中点能到的最大的正方形, 设其边长为l, 则答案多了l-1个
难点只有一个 : 四个哈希的前缀取的坐标是不一样的.
分奇偶在草纸上画一下就可以了, 这个一定要先理清再写
不卡自然溢出, 不用加模数
代码 :
#include
#include
#include
#include
#include
using namespace std;
const int N = 1010;
const int b1 = 131;
const int b2 = 1313131;
#define ull unsigned long long
#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 10000, stdin), p1==p2)?EOF:*p1++
char buf[100000], *p1, *p2;
inline char gc() {
char ch = nc();
while(isspace(ch)) ch = nc();
return ch;
}
inline int rd() {
int x = 0, f = 1; char ch = nc();
while(!isdigit(ch)) ch = nc();
while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc();
return x*f;
}
int n, m;
int a[N][N];
long long ans;
ull mi1[N], mi2[N];
ull h1[N][N], h2[N][N], h3[N][N], h4[N][N];
inline void getHash() {
for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ )
h1[i][j] = h1[i-1][j]*b1+h1[i][j-1]*b2-h1[i-1][j-1]*b1*b2+a[i][j];
for(int i = 1; i <= n; i ++ ) for(int j = m; j >= 1; j -- )
h2[i][j] = h2[i-1][j]*b1+h2[i][j+1]*b2-h2[i-1][j+1]*b1*b2+a[i][j];
for(int i = n; i >= 1; i -- ) for(int j = 1; j <= m; j ++ )
h3[i][j] = h3[i+1][j]*b1+h3[i][j-1]*b2-h3[i+1][j-1]*b1*b2+a[i][j];
for(int i = n; i >= 1; i -- ) for(int j = m; j >= 1; j -- )
h4[i][j] = h4[i+1][j]*b1+h4[i][j+1]*b2-h4[i+1][j+1]*b1*b2+a[i][j];
}
inline void getAns() {
register int l, r, mid;
ull a1, a2, a3, a4;
for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) {
// PART I
l = 1, r = min( min(i, j), min(n-i+1, m-j+1) )+1;
while(l < r) {
mid = (l+r) >> 1;
a1 = h1[i][j]-h1[i-mid][j]*mi1[mid]-h1[i][j-mid]*mi2[mid]+h1[i-mid][j-mid]*mi1[mid]*mi2[mid];
a2 = h2[i][j]-h2[i-mid][j]*mi1[mid]-h2[i][j+mid]*mi2[mid]+h2[i-mid][j+mid]*mi1[mid]*mi2[mid];
a3 = h3[i][j]-h3[i+mid][j]*mi1[mid]-h3[i][j-mid]*mi2[mid]+h3[i+mid][j-mid]*mi1[mid]*mi2[mid];
a4 = h4[i][j]-h4[i+mid][j]*mi1[mid]-h4[i][j+mid]*mi2[mid]+h4[i+mid][j+mid]*mi1[mid]*mi2[mid];
if(a1 == a2 && a2 == a3 && a3 == a4) l = mid+1;
else r = mid;
}
ans += l-1;
// PART II
l = 1, r = min( min(i, j), min(n-i, m-j) )+1;
while(l < r) {
mid = (l+r) >> 1;
a1 = h1[i][j]-h1[i-mid][j]*mi1[mid]-h1[i][j-mid]*mi2[mid]+h1[i-mid][j-mid]*mi1[mid]*mi2[mid];
j ++, a2 = h2[i][j]-h2[i-mid][j]*mi1[mid]-h2[i][j+mid]*mi2[mid]+h2[i-mid][j+mid]*mi1[mid]*mi2[mid];
i ++, j --, a3 = h3[i][j]-h3[i+mid][j]*mi1[mid]-h3[i][j-mid]*mi2[mid]+h3[i+mid][j-mid]*mi1[mid]*mi2[mid];
j ++, a4 = h4[i][j]-h4[i+mid][j]*mi1[mid]-h4[i][j+mid]*mi2[mid]+h4[i+mid][j+mid]*mi1[mid]*mi2[mid];
i --, j --;
if(a1 == a2 && a2 == a3 && a3 == a4) l = mid+1;
else r = mid;
}
ans += l-1;
}
}
int main() {
n = rd(), m = rd(); mi1[0] = mi2[0] = 1;
for(int i = 1; i <= n; i ++ ) mi1[i] = mi1[i-1]*b1, mi2[i] = mi2[i-1]*b2;
for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) a[i][j] = rd();
getHash();
getAns();
printf("%lld\n", ans);
}
本文为Yirannn原创, 转载必须以链接形式注明>原文链接<