本文共 3001 字，大约阅读时间需要 10 分钟。
传送门：
多校赛的时候根本不知道如何下手，怎么算复杂度都是爆表的，根据题解说复杂度是O(1e3^2*64)，感觉好像是这个道理，于是就用HashMap的模板敲了一遍，结果还真的过了（比标程快了一倍）
首先暴力比较肯定是不可取的（毕竟1e6*1e6的矩阵），我们可以在大矩阵中取一个小矩阵，这里取一个1*64的矩阵，然后跟1e3*1e3的矩阵进行比较，如果小矩阵在这个1e3*1e3的矩阵中，那么我们可以通过小矩阵确定这个1e3*1e3的矩阵的位置（实在不放心，还可以在判断一下这个矩阵是否在这个位置）。为了节约时间可以直接用unsigned long long来存储这个1*64的矩阵，运算时也多用位运算。
那么如何枚举小矩阵呢？（全部枚举显然是不行的），这里主要用到鸽巢原理，假如这次枚举的小矩阵左上角的位置为(x,y)，上次枚举的位置为(x',y')，那么只要x-x'<1e3且y-y'+64<1e3那么枚举的过程中一定不会“错过”这个1e3*1e3的矩阵，于是就可以将枚举量减小到1e6
#includeusing namespace std;typedef long long LL;typedef unsigned long long ULL;const int sz = 64;const int MX = 1e3;const int MXN = 1e6 + 7;//哈希表节点个数，用来平分链的长度const int MXM = 1e6 + 5;//链的总长度struct HashMap { int head[MXN], tot; struct node { ULL f, state; int nxt; } E[MXM]; void init() { tot = 0; memset(head, -1, sizeof(head)); } void push(ULL st, LL val) { int u = st % MXN; for (int i = head[u]; ~i; i = E[i].nxt) { if (E[i].state == st) { E[i].f += val; return; } } E[tot].state = st; E[tot].f = val; E[tot].nxt = head[u]; head[u] = tot++; } inline ULL find(ULL st) { int u = st % MXN; for (int i = head[u]; ~i; i = E[i].nxt) if (E[i].state == st) return E[i].f; return 0; }} hm;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;}ULL a[MX + 5][MX + 5];bool check(int x, int y) { ULL t = 0; for (int i = 0; i < MX; i++) { for (int j = 0; j + sz < MX; j += sz) { for (int k = 0; k < sz; k++) t = t << 1 | f(x + i, y + j + k); if (a[i + 1][j + 1] != t) return false; } } return true;}char str[MX * 10];int main() { int T, cas = 0, mx = 1e6; scanf("%d", &T); while (T--) { hm.init(); for (LL i = 1; i <= MX; i++) { scanf("%s", str + 1); ULL x = 0; for (int j = 1; j <= sz; j++) x = x << 1 | (str[j] == '1'); hm.push(x, i * MX + 1); a[i][1] = x; for (int j = 2; j + sz <= MX; j++) { x = x << 1 | (str[j + sz - 1] == '1'); hm.push(x, i * MX + j); a[i][j] = x; } } bool flag = 1; for (LL i = 1; flag && i <= mx; i += 1000) { for (int j = 1; flag && j + sz <= mx; j += 900) { ULL x = 0; for (int k = 0; k < sz; k++) x = x << 1 | f(i, j + k); LL ret = hm.find(x); if (ret) { int sx = i + 1 - (ret / MX), sy = j + 1 - (ret % MX); printf("Case #%d :%d %d\n", ++cas, sx, sy); flag = 0; } } } } return 0;}
转载地址：http://kpwpn.baihongyu.com/