10pts求助!!!
查看原帖
10pts求助!!!
609565
OtterZ楼主2023/1/17 22:04
#include<iostream>
#include<cstdio>
#include<algorithm>
typedef unsigned long long ULL;
using namespace std;
const int p=31,q=233,N=1009;
ULL h[N][N],pp[N],qq[N],h2[N][N],h3[N][N];
int n,m,x,y;
unsigned long long t;
int c1[N][N],c2[N][N],c3[N][N];
void make_hash(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h[i][j]=h[i][j-1]*q+h[i-1][j]*p-h[i-1][j-1]*p*q+c1[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h2[i][j]=h2[i][j-1]*q+h2[i-1][j]*p-h2[i-1][j-1]*p*q+c2[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h3[i][j]=h3[i][j-1]*q+h3[i-1][j]*p-h3[i-1][j-1]*p*q+c3[i][j];
    pp[0]=qq[0]=1;
    for(int i=1;i<=n||i<=m;i++){pp[i]=pp[i-1]*p,qq[i]=qq[i-1]*q;}
}
ULL query(int x1,int y1,int x2,int y2){
    return h[x2][y2]-h[x1-1][y2]*pp[x2-x1+1]-h[x2][y1-1]*qq[y2-y1+1]+h[x1-1][y1-1]*pp[x2-x1+1]*qq[y2-y1+1];
}
ULL query2(int x1,int y1,int x2,int y2){
    return h2[x2][y2]-h2[x1-1][y2]*pp[x2-x1+1]-h2[x2][y1-1]*qq[y2-y1+1]+h2[x1-1][y1-1]*pp[x2-x1+1]*qq[y2-y1+1];
}
ULL query3(int x1,int y1,int x2,int y2){
    return h3[x2][y2]-h3[x1-1][y2]*pp[x2-x1+1]-h3[x2][y1-1]*qq[y2-y1+1]+h3[x1-1][y1-1]*pp[x2-x1+1]*qq[y2-y1+1];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&c1[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c2[i][j]=c1[n+1-i][j];
            c3[i][j]=c1[i][m+1-j];
        }
    }
    make_hash();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int l=1,r=min(n-i+1,min(i,min(m-j+1,j)))+1;
            while(r-l>1){
                int mid=(l+r)/2;
                if(query(i-mid+1,j-mid+1,i+mid-1,j+mid-1)==query2(n-i-mid+2,j-mid+1,n-i+mid,j+mid-1)&&query(i-mid+1,j-mid+1,i+mid-1,j+mid-1)==query3(i+mid-1,m-j-mid+2,i+mid-1,m-j+mid))l=mid;
                else r=mid;
            }
            t+=l;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            int l=0,r=min(n-i,min(i,min(m-j,j)))+1;
            while(r-l>1){
                int mid=(l+r)/2;
                if(query(i-mid+1,j-mid+1,i+mid,j+mid)==query2(n-i-mid+1,j-mid+1,n-i+mid,j+mid)&&query(i-mid+1,j-mid+1,i+mid,j+mid)==query3(i-mid+1,m-j-mid+1,i+mid,m-j+mid))l=mid;
                else r=mid;
            }
            t+=l;
        }
    }
    printf("%d\n",t);
    return 0;
}

2023/1/17 22:04
加载中...