网站建设服务费进入什么科目,婚庆公司收费标准价目一览表,wordpress访问多站点,企业平台网P2601 [ZJOI2009] 对称的正方形
题目大意
给定一个 n m n\times m nm的矩阵#xff0c;求这个矩阵中满足上下对称且左右对称的正方形子矩阵的个数。 1 ≤ n , m ≤ 1000 1\leq n,m\leq 1000 1≤n,m≤1000 题解
首先#xff0c;我们对原矩阵、左右翻转后的矩阵、上下翻转后…P2601 [ZJOI2009] 对称的正方形
题目大意
给定一个 n × m n\times m n×m的矩阵求这个矩阵中满足上下对称且左右对称的正方形子矩阵的个数。 1 ≤ n , m ≤ 1000 1\leq n,m\leq 1000 1≤n,m≤1000 题解
首先我们对原矩阵、左右翻转后的矩阵、上下翻转后的矩阵分别做二维哈希的处理。
对于边长为偶数的正方形枚举正方形中心的格点并二分最远的符合题意的长度。
对于边长为奇数的正方形枚举正方形中心的各自并二分最远的符合题意的长度。
判断是否符合题意可以通过判断三个矩阵中对应位置的二维哈希值是否相等来得到。
最后记得加上单个格子的贡献。
时间复杂度为 O ( n m log min ( n , m ) ) O(nm\log \min(n,m)) O(nmlogmin(n,m))。
code
#includebits/stdc.h
using namespace std;
const int N1000;
const int bs1131,bs2233;
const long long mod1e97;
int n,m,a[N5][N5],b[N5][N5],c[N5][N5];
long long ans0,f1[N5],f2[N5];
long long s1[N5][N5],s2[N5][N5],s3[N5][N5];
long long gt1(int ux,int uy,int dx,int dy){return s1[dx][dy]-s1[dx][uy-1]*f1[dy-uy1]%mod-s1[ux-1][dy]*f2[dx-ux1]%mods1[ux-1][uy-1]*f1[dy-uy1]%mod*f2[dx-ux1]%mod;
}
long long gt2(int ux,int uy,int dx,int dy){return s2[dx][dy]-s2[dx][uy-1]*f1[dy-uy1]%mod-s2[ux-1][dy]*f2[dx-ux1]%mods2[ux-1][uy-1]*f1[dy-uy1]%mod*f2[dx-ux1]%mod;
}
long long gt3(int ux,int uy,int dx,int dy){return s3[dx][dy]-s3[dx][uy-1]*f1[dy-uy1]%mod-s3[ux-1][dy]*f2[dx-ux1]%mods3[ux-1][uy-1]*f1[dy-uy1]%mod*f2[dx-ux1]%mod;
}
bool check(int ux,int uy,int dx,int dy){if(ux1||uy1||dxn||dym) return 0;long long v1,v2,v3;v1(gt1(ux,uy,dx,dy)%modmod)%mod;v2(gt2(n-dx1,uy,n-ux1,dy)%modmod)%mod;v3(gt3(ux,m-dy1,dx,m-uy1)%modmod)%mod;return v1v2v2v3;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j){scanf(%d,a[i][j]);b[n-i1][j]a[i][j];c[i][m-j1]a[i][j];}}f1[0]f2[0]1;for(int i1;imin(n,m);i){f1[i]f1[i-1]*bs1%mod;f2[i]f2[i-1]*bs2%mod;}for(int i1;in;i){for(int j1;jm;j){s1[i][j](s1[i][j-1]*bs1a[i][j])%mod;s2[i][j](s2[i][j-1]*bs1b[i][j])%mod;s3[i][j](s3[i][j-1]*bs1c[i][j])%mod;}}for(int i1;in;i){for(int j1;jm;j){s1[i][j](s1[i-1][j]*bs2s1[i][j])%mod;s2[i][j](s2[i-1][j]*bs2s2[i][j])%mod;s3[i][j](s3[i-1][j]*bs2s3[i][j])%mod;}}for(int i1;in;i){for(int j1;jm;j){int l1,rn,mid;while(lr){midlr1;if(check(i-mid1,j-mid1,imid,jmid)) lmid1;else rmid-1;}ansl-1;}}for(int i1;in;i){for(int j1;jm;j){int l1,rn,mid;while(lr){midlr1;if(check(i-mid,j-mid,imid,jmid)) lmid1;else rmid-1;}ansl-1;}}ansn*m;printf(%lld,ans);return 0;
}
