题目传送门(BZOJ)

题解 :

显然且麻烦的一个二维矩阵哈希

对于矩阵对称的处理就像对于回文的处理一样即可.

但是要维护四个哈希 : 左上/右上/左下/右下 的哈希

注意行和列要用不同的BASE,

然后O(NM)枚举中点, 分奇偶二分出当前中点能到的最大的正方形, 设其边长为l, 则答案多了l-1

难点只有一个 : 四个哈希的前缀取的坐标是不一样的.

分奇偶在草纸上画一下就可以了, 这个一定要先理清再写

不卡自然溢出, 不用加模数

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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原创, 转载必须以链接形式注明>原文链接<