「Bzoj 2351」「BeiJing2011」Matrix (二维Hash)

BZOJ 2351
题意：给定$n \times m$大小矩阵，$q$次询问$a \times b$大小矩阵是否是大矩阵的一部分。

给行列分别hash一次，行先hash，然后将hash值再hash一次，即hash列

然后查询子矩阵Hash值直接像二维前缀和一样做即可，类比于一维的 Hash 方法

知识点：
1、二维Hash
2、Hash值选取
3、Hash的方法取决于是否会冲突，这里运用不同模数巧妙解决冲突

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int m, n, a, b, q;
    unsigned LL bs1 = 257, bs2 = 259, hsh[1005][1005], p1[1005], p2[1005], whw[1005][1005];
    map<unsigned LL, bool > ma;

    void clean() {
        ms(whw, 0), ms(hsh, 0);
    }
    int solve() {
        clean();
        scanf("%d%d%d%d", &m, &n, &a, &b);
        for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) scanf("%1lld", &hsh[i][j]), ++hsh[i][j];
        scanf("%d", &q);
        if (m < a || n < b) {
            while (q--) printf("0\n");
            return 0;
        }
        for (int i = 1; i <= m; ++i) 
        for (int j = 1; j <= n; ++j) hsh[i][j] += hsh[i - 1][j] * bs1; 
        for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) hsh[i][j] += hsh[i][j - 1] * bs2;
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= 1000; ++i) p1[i] = p1[i - 1] * bs1;
        for (int i = 1; i <= 1000; ++i) p2[i] = p2[i - 1] * bs2;

        for (int i = a; i <= m; ++i) 
        for (int j = b; j <= n; ++j) ma[hsh[i][j] - hsh[i - a][j] * p1[a] - hsh[i][j - b] * p2[b] + hsh[i - a][j - b] * p1[a] * p2[b]] = true;

        while (q--) {
            for (int i = 1; i <= a; ++i)
            for (int j = 1; j <= b; ++j) scanf("%1lld", &whw[i][j]), ++whw[i][j];
            for (int i = 1; i <= a; ++i)
            for (int j = 1; j <= b; ++j) whw[i][j] += whw[i - 1][j] * bs1;
            for (int i = 1; i <= a; ++i)
            for (int j = 1; j <= b; ++j) whw[i][j] += whw[i][j - 1] * bs2;
            map<unsigned LL, bool >::iterator it = ma.find(whw[a][b]);
            if (it != ma.end()) {
                if (it->second == true) printf("1\n"); else printf("0\n");
            } else printf("0\n");
        }

        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}