bzoj2351 Matrix（二维哈希）

灰太狼 2021-10-18 14:46 230阅读 0赞

## 题意： ##

Description   
给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在原矩阵中出现过。   
所谓01矩阵，就是矩阵中所有元素不是0就是1。   
Input   
输入文件的第一行为M、N、A、B，参见题目描述。   
接下来M行，每行N个字符，非0即1，描述原矩阵。   
接下来一行为你要处理的询问数Q。   
接下来Q个矩阵，一共Q\*A行，每行B个字符，描述Q个01矩阵。   
Output   
你需要输出Q行，每行为0或者1，表示这个矩阵是否出现过，0表示没有出现过，1表示出现过。   
Sample Input   
3 3 2 2   
111   
000   
111   
3   
11   
00   
11   
11   
00   
11   
Sample Output   
1   
0   
1   
HINT   
对于100%的实际测试数据，M、N ≤ 1000，Q = 1000   
对于40%的数据，A = 1。   
对于80%的数据，A ≤ 10。   
对于100%的数据，A ≤ 100。

## 分析：二维哈希模板题，先计算哈希前缀和，再通过容斥求出原矩阵中出现所有的a\*b大小的子矩阵的哈希值，存入map，判断是否查询即可。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ull unsigned long long
    #define N 1010
    #define k1 11113
    #define k2 11117
    int n,m,a,b,q;
    map<ull,int>mp;
    ull hs[N][N],bin1[N],bin2[N];
    char s[N];
    
    int main() {
        scanf("%d%d%d%d",&n,&m,&a,&b);
        bin1[0]=bin2[0]=1;
        for(int i=1;i<=n;++i) {
            scanf("%s",s+1);
            for(int j=1;j<=m;++j)
                hs[i][j]=hs[i][j-1]*k1+s[j];
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                hs[i][j]+=hs[i-1][j]*k2;
        for(int i=1;i<=n;++i)
            bin2[i]=bin2[i-1]*k2;
        for(int i=1;i<=m;++i)
            bin1[i]=bin1[i-1]*k1;
        for(int i=a;i<=n;++i)
            for(int j=b;j<=m;++j)
                mp[hs[i][j]-hs[i-a][j]*bin2[a]-hs[i][j-b]*bin1[b]+hs[i-a][j-b]*bin2[a]*bin1[b]]=1;///容斥
        scanf("%d",&q);
        while(q--) {
            ull res=0;
            for(int i=1;i<=a;++i) {
                scanf("%s",s+1);
                for(int j=1;j<=b;++j)
                    res+=s[j]*bin2[a-i]*bin1[b-j];
            }
            if(mp[res]) printf("1\n");
            else printf("0\n");
        }
        return 0;
    }