题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2351
就是先把每行单独从左到右扫着乘一个 b1 哈希起来，然后再按列从上往下乘一个 b2 哈希起来。
如果要取模的话，行的哈希和列的哈希应该模一样的数。
当然不是读入询问再枚举所有位置看哈希值啦……应该先把合法位置的哈希值用一个 map 之类的存一下存在性，询问的时候直接查 map 就行了。
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ull unsigned long long using namespace std; const int N=1005,b1=1e9+7,b2=993244853; int n,m,a,b; ull bn1[N],bn2[N],hs[N][N]; map<ull,bool> mp; int main() { scanf("%d%d%d%d",&n,&m,&a,&b); bn1[0]=1;for(int i=1;i<=n;i++)bn1[i]=bn1[i-1]*b1; bn2[0]=1;for(int i=1;i<=m;i++)bn2[i]=bn2[i-1]*b2; for(int i=1,d;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%1d",&d); d++;// hs[i][j]=hs[i][j-1]*b2+d; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) hs[i][j]=hs[i-1][j]*b1+hs[i][j]; for(int i=a;i<=n;i++) for(int j=(i==a?b:1);j<=m;j++) { ull tp=hs[i][j] - hs[i-a][j]*bn1[a] - hs[i][j-b]*bn2[b] + hs[i-a][j-b]*bn1[a]*bn2[b]; mp[tp]=1; } int Q; scanf("%d",&Q); while(Q--) { ull tmp=0; for(int i=1,d;i<=a;i++) for(int j=1;j<=b;j++) { scanf("%1d",&d); d++; tmp+=d*bn1[a-i]*bn2[b-j]; } puts(mp[tmp]?"1":"0"); } return 0; }
bzoj 2351 [BeiJing2011]Matrix——二维哈希
原文：https://www.cnblogs.com/Narh/p/10447262.html