题目描述
给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在原矩阵中出现过。
所谓01矩阵，就是矩阵中所有元素不是0就是1。
输入
输入文件的第一行为M、N、A、B，参见题目描述。
接下来M行，每行N个字符，非0即1，描述原矩阵。
接下来一行为你要处理的询问数Q。
接下来Q个矩阵，一共Q*A行，每行B个字符，描述Q个01矩阵。
输出
你需要输出Q行，每行为0或者1，表示这个矩阵是否出现过，0表示没有出现过，1表示出现过。
样例输入
3 3 2 2
111
000
111
3
11
00
11
11
00
11
样例输出
1
0
1
题解
二维Hash
因为一维Hash就是一维前缀和，所以二维Hash就是二维前缀和——GXZlegend
事实上的确是这样的，维护矩阵 $(1...n,1...m)$ 的Hash值的方法与二维前缀和类似，利用容斥关系推出。其中，设行列两个base，然后乘上base相加减即可。
由于每次询问的 $a$ 和 $b$ 相同，因此预处理出所有原矩阵的 $a × b$ 的子矩阵的Hash值，存到哈希表中，查询时直接找是否有相等的Hash值即可。
注意：行列base不能相同（不然沿主对角线反转Hash值不变）；01串的Hash不能以0和1作为取值，应以'0'和'1'作为取值。
具体看代码吧。
时间复杂度 $O(nm+qab)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
#define M 12345678
using namespace std;
typedef unsigned long long ull;
struct data
{
int head[M] , next[N * N] , tot;
ull v[N * N];
inline void insert(ull x)
{
if(!head[x % M]) head[x % M] = ++tot , v[tot] = x;
else
{
int i;
for(i = head[x % M] ; next[i] ; i = next[i])
if(v[i] == x)
return;
next[i] = ++tot , v[tot] = x;
}
}
inline int count(ull x)
{
int i;
for(i = head[x % M] ; i ; i = next[i])
if(v[i] == x)
return 1;
return 0;
}
}mp;
ull v[N][N] , w[N][N];
char str[N];
int main()
{
int n , m , a , b , q , i , j;
ull c = 1 , d = 1;
scanf("%d%d%d%d" , &n , &m , &a , &b);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%s" , str + 1);
for(j = 1 ; j <= m ; j ++ )
v[i][j] = str[j] + v[i][j - 1] * 233 + v[i - 1][j] * 2333 - v[i - 1][j - 1] * 233 * 2333;
}
for(i = 1 ; i <= b ; i ++ ) c *= 233;
for(i = 1 ; i <= a ; i ++ ) d *= 2333;
for(i = a ; i <= n ; i ++ )
for(j = b ; j <= m ; j ++ )
mp.insert(v[i][j] - v[i][j - b] * c - v[i - a][j] * d + v[i - a][j - b] * c * d);
scanf("%d" , &q);
while(q -- )
{
for(i = 1 ; i <= a ; i ++ )
{
scanf("%s" , str + 1);
for(j = 1 ; j <= b ; j ++ )
w[i][j] = str[j] + w[i][j - 1] * 233 + w[i - 1][j] * 2333 - w[i - 1][j - 1] * 233 * 2333;
}
printf("%d\n" , mp.count(w[a][b]));
}
return 0;
}