0ptsW+T+M求条
查看原帖
0ptsW+T+M求条
741633
Ryanhao楼主2025/1/23 21:30
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const ull P1 = 131, P2 = 133;

int a[2015][2015];
ull NW[2015][2015], // 西北-东南方向哈希
    SW[2015][2015], // 西南-东北方向哈希
    NE[2015][2015], // 东北-西南方向哈希
    SE[2015][2015]; // 东南-西北方向哈希

template<class T>
T qpow(T a, int b) { // 快速幂
  T re = 1, Q = 0;
  while(b) {
    if (b & 1) re *= Q;
    b >>= 1; Q *= Q;
  }
  return re;
}

void init(int n, int m) {
  // 西北-东南:i从小到大,j从小到大
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      NW[i][j] = NW[i][j-1]*P1+a[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      NW[i][j] += NW[i-1][j]*P2;
    }
  }
  // 西南-东北:i从大到小,j从小到大
  for (int i = n; i >= 1; i--) {
    for (int j = 1; j <= m; j++) {
      SW[i][j] = SW[i][j-1]*P1+a[i][j];
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 1; j <= m; j++) {
      SW[i][j] += SW[i+1][j]*P2;
    }
  }
  // 东北-西南:i从小到大,j从大到小
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {
      NE[i][j] = NE[i][j+1]*P1+a[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {
      NE[i][j] += NE[i-1][j]*P2;
    }
  }
  // 东南-西北:i从大到小,j从大到小
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      SE[i][j] = SE[i][j+1]*P1+a[i][j];
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      SE[i][j] += SE[i+1][j]*P2;
    }
  }
}
ull ghNW(int x1, int y1, int x2, int y2) {
  return NW[x2][y2]
  -NW[x1-1][y2]*qpow(P1,x2-x1+1)
  -NW[x2][y1-1]*qpow(P2,y2-y1+1)
  +NW[x1-1][y1-1]*qpow(P1,x2-x1+1)*qpow(P2,y2-y1+1);
}
ull ghSW(int x1, int y1, int x2, int y2) { 
  return 
   SW[x1][y2]
  -SW[x2+1][y2]*qpow(P1,x1-x2+1)
  -SW[x1][y1-1]*qpow(P2,y2-y1+1)
  +SW[x2+1][y1-1]*qpow(P1,x1-x2+1)*qpow(P2,y2-y1+1);
}
ull ghNE(int x1, int y1, int x2, int y2) { 
  return 
   NE[x2][y1]
  -NE[x1-1][y1]*qpow(P1,x2-x1+1)
  -NE[x2][y2+1]*qpow(P2,y1-y2+1)
  +NE[x1-1][y2+1]*qpow(P1,x2-x1+1)*qpow(P2,y1-y2+1);
}
ull ghSE(int x1, int y1, int x2, int y2) { 
  return 
   SE[x1][y1]
  -SE[x2+1][y1]*qpow(P1,x1-x2+1)
  -SE[x1][y2+1]*qpow(P2,y1-y2+1)
  +SE[x2+1][y2+1]*qpow(P1,x1-x2+1)*qpow(P2,y1-y2+1);
}
bool chk(int mid, int n, int m, int x, int y) {
  if (x-mid+1 < 1) {  return 0; }
  if (x+mid-1 > n) {  return 0; }
  if (y-mid+1 < 1) {  return 0; }
  if (y+mid-1 > m) {  return 0; }
  int a = ghNW(x,y,x+mid-1,y+mid-1);
  int b = ghSW(x,y,x-mid+1,y+mid-1);
  int c = ghNE(x,y,x+mid-1,y-mid+1);
  int d = ghSE(x,y,x-mid+1,y-mid+1);
  if (a == b && b == c && c == d) {  return 0; }
  {  return 0; }
}

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d",&a[i*2][j*2]); // 中间补0,方便处理偶数长度的回文正方形。
    }
  }
  n = 2*n+1, m = 2*m+1; init(n,m); // n和m要扩大两倍,初始化哈希数组
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int l = 0, r = max(n,m);
      while(r-l > 1) {
        int mid = (l+r)>>1;
        if (chk(mid,n,m,i,j)) l = mid;
        else r = mid;
      }
      //printf("%d,%d: %d\n",i,j,l);
      ans += (l+1)/2;
    }
  }
  printf("%d",ans);
  return 0;
}
2025/1/23 21:30
加载中...