BZOJ2462: [BeiJing2011]矩阵模板(二维hash)

题意

题目链接

sol

二维矩阵hash，就是对行和列分配一个不同的base，然后分别做一遍hash，这样会减少冲突的概率。

预处理出所有大小为\(a \times b\)的矩阵的hash值，判断一下即可

mdzz居然卡常数

#include<bits/stdc++.h>
#define ull unsigned int
using namespace std;
const int maxn = 1010, mod = 100000007;
const ull base1 = 19260817, base2 = 998244353;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, a, b;
ull po1[maxn], po2[maxn], m[maxn][maxn], a[maxn][maxn];
bool ha[mod + 1];
int readch() {
    char c = '.';
    while(c != '0' && c != '1') c = getchar();
    return c;
}
main() {
    //freopen("1.in", "r", stdin);
    n = read(); m = read(); a = read(); b = read();
    po1[0] = 1; for(int i = 1; i <= n; i++) po1[i] = po1[i - 1] * base1;
    po2[0] = 1; for(int i = 1; i <= m; i++) po2[i] = po2[i - 1] * base2;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) m[i][j] = readch();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            m[i][j] += m[i - 1][j] * base1;
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            m[i][j] += m[i][j - 1] * base2;
    for(int i = a; i <= n; i++) {
        for(int j = b; j <= m; j++) {
            ull tmp = m[i][j] - m[i - a][j] * po1[a] - m[i][j - b] * po2[b] + m[i - a][j - b] * po1[a] * po2[b];
            ha[tmp % mod] = 1;
        }
    }
    int q = read();
    while(q--) {
        for(int i = 1; i <= a; i++) for(int j = 1; j <= b; j++) a[i][j] = readch();
        for(int i = 1; i <= a; i++)
            for(int j = 1; j <= b; j++)
                a[i][j] += a[i - 1][j] * base1;
        for(int i = 1; i <= a; i++) 
            for(int j = 1; j <= b; j++)
                a[i][j] += a[i][j - 1] * base2;
        putchar(ha[a[a][b] % mod] ? '1' : '0'); putchar('\n');
    }
    return 0;
}