HDU 6046 hash （HASH, 2017 Multi-Univ Training Contest 2）

Problem

106×106 的 01 矩阵（记作 A ）根据下列提供函数给定，f(x, y) 表示该矩阵的 x 行 j 列的数

inline unsigned sfr(unsigned h, unsigned x) { return h >> x; } int f(LL i, LL j) { LL w = i * 1000000ll + j; int h = 0; for(int k = 0; k < 5; ++k) { h += (int) ((w >> (8 * k)) & 255); h += (h << 10); h ^= sfr(h, 6); } h += h << 3; h ^= sfr(h, 11); h += h << 15; return sfr(h, 27) & 1; }

提供 1000×1000 的矩阵 B ，要求判断其在 A 矩阵中的位置。

Idea

由于 A 矩阵过大，纵然想要先行获取其每位的数值，在时间复杂度内也是不允许的。

考虑将 B 矩阵按 8×8 的矩阵样式获取其每个子矩阵（总数近 106 个）的 hash 值，并记录。

将 A 矩阵严格划分为 1000×1000 的子矩阵 subA （共 1000×1000 个）。

则获取每个 subA 的左上 8×8 和右下 8×8 ，必然至少存在一个恰好与 B 矩阵中的 8×8 矩阵的 hash 值相同。

对获取到的矩阵判断其是否与 B 矩阵完全相同即可（也可不必判断，由于 A 矩阵完全随机，故碰撞的概率很小）。

Code

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; const int HASH_SEED = 1999997; int T, ica = 1; unsigned long long num, g[HASH_SEED]; char b[1010][1010]; int b8[1010][1010], x[HASH_SEED], y[HASH_SEED]; void HASH(int i, int j) { int hash = num % HASH_SEED; while(g[hash]) { if(++hash == HASH_SEED) hash = 0; } g[hash] = num; x[hash] = i; y[hash] = j; } inline unsigned sfr(unsigned h, unsigned x) { return h >> x; } int f(long long i, long long j) { long long w = i * 1000000ll + j; int h = 0; for(int k = 0; k < 5; ++k) { h += (int) ((w >> (8 * k)) & 255); h += (h << 10); h ^= sfr(h, 6); } h += h << 3; h ^= sfr(h, 11); h += h << 15; return sfr(h, 27) & 1; } bool jug(int x, int y) { if(x <= 0 || y <= 0) return false; for(int i=0;i<1000;i++) for(int j=0;j<1000;j++) if(f(x+i, y+j) != b[i+1][j+1]-'0') return false; return true; } bool solveHash(int i, int j) { num = 0; for(int ii=0;ii<8;ii++) for(int jj=0;jj<8;jj++) { num <<= 1; num += f(i+ii, j+jj); } int hash = num % HASH_SEED; while(g[hash]) { if(g[hash] == num) { printf("Case #%d :%d %d\n", ica++, i-x[hash]+1, j-y[hash]+1); return true; } if(++hash == HASH_SEED) hash = 0; } return false; } void solve() { for(int i=1;i<1000000;i+=1000) for(int j=1;j<1000000;j+=1000) if(solveHash(i, j) || solveHash(i+1000-7, j+1000-7)) return; } int main() { scanf("%d", &T); while(ica <= T) { memset(g, 0, sizeof(g)); for(int i=1;i<=1000;i++) { scanf(" %s", b[i]+1); num = 0; for(int j=1;j<=7;j++) num<<=1, num += b[i][j]-'0'; for(int j=8;j<=1000;j++) { num<<=1, num+=b[i][j]-'0'; num %= 256; b8[i][j-7] = num; } } for(int i=1;i<=1000-7;i++) for(int j=1;j<=1000-7;j++) { num = 0; for(int k=0;k<8;k++) num<<=8, num += b8[i+k][j]; HASH(i, j); } solve(); } }