思路来自题解和一些博客
最麻烦的是样例没啥用- -
/*
HDU 6046 - hash [ hash,鸽巢 ] | 2017 Multi-University Training Contest 2
题意：
给出一个1e3*1e3的矩阵以及 一个 生成1e6*1e6的矩阵的随机函数
在1e6*1e6的矩阵中找到1e3*1e3的矩阵的位置
分析：
将1e3*1e3的矩阵每一个位置压入哈希表中，哈希值为其与之后63位所组成64位的值（不满64位就不压入）
由于 2^64 远大于 1e12 故可认为哈希值相同的是同一个位置
枚举大矩阵中的位置，若能在哈希表中找到这个位置的哈希值，则小矩阵头部的相对位置可以确定
但不需要枚举大矩阵中的每个位置，可以每隔1000行，隔900列枚举一个位置
这样根据鸽巢原理，枚举的这些位置至少有一个被小矩阵覆盖
选隔900列而不是1000列的原因是 小矩阵每行最右端63个点没被压入哈希表，所以哈希表中的矩阵是 1000 * (1000-63)的
*/
#include <bits/stdc++.h>
using namespace std;
#define LL unsigned long long
const int N = 1e3+5;
const int L = 1000;
const int ZIP = 64;
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;
}
namespace HashMap{
const int MOD = 1313131;
struct Node {
LL pos, val;
int nxt;
}node[N*N];
int head[MOD], tot;
void init() {
memset(head, 0, sizeof(head));
tot = 0;
}
void insert(LL v, LL p) {
int t = v % MOD; tot++;
node[tot].pos = p;
node[tot].val = v;
node[tot].nxt = head[t];
head[t] = tot;
}
LL find(LL v) {
for (int i = head[v%MOD]; i; i = node[i].nxt)
if (node[i].val == v) return node[i].pos;
return 0;
}
}
char s[N];
LL hs[N];
int main()
{
int t; scanf("%d", &t);
for (int tt = 1; tt <= t; tt++)
{
HashMap::init();
for (int i = 1; i <= L; i++)
{
scanf("%s", s+1);
hs[L+1] = 0;
for (int j = L; j >= 1; j--)
hs[j] = hs[j+1]<<1|(s[j]-'0');
for (int j = 1; j <= L-ZIP+1; j++)
HashMap::insert(hs[j], i*1024+j);
}
LL ans = 0; int x, y;
for (int i = 1; i <= 1e6 && (!ans); i += 1000)
for (int j = 1; j <= 1e6 && (!ans); j += 900)
{
if (j+ZIP-1 > 1e6) continue;
LL val = 0;
for (int k = ZIP-1; k >= 0; k--)
val = val<<1|(f(i,j+k));
ans = HashMap::find(val);
if (ans != 0) x = i, y = j;
}
int px = x - ans / 1024 + 1, py = y - ans % 1024 + 1;
printf("Case #%d :%d %d
", tt, px, py);
}
}