矩阵哈希

引入

矩阵哈希，又称二维前缀哈希。联系之前学习过的 字符串哈希，不难得出矩阵哈希的实质：将每个不同的矩阵映射为不同的整数，期望 \(O(1)\) 地比较矩阵是否相同。
对于一个 \(n\) 行 \(m\) 列的矩阵 \(A\)，定义它的矩阵 Hash 值为：

\[\sum_{i=1}^{n}\sum_{j=1}^{m}A_{i,j} \ p_x^{n-i}p_y^{m-j}\]
类似于二维前缀和的推导过程，我们得出以下两条矩阵哈希的核心结论：

• 点 \((i, j)\) 的矩阵前缀 Hash 值的计算公式为：
  

\[H(i,j) = H(i-1,j)p_x + H(i,j-1)p_y - H(i-1,j-1)p_x p_y + a_{i,j}\]

解释： 如上图，蓝色的矩形右下角为 \(H(i,j-1)\)，绿色的矩形右下角为 \(H(i,j-1)\)，它们重合部分的紫色矩形右下角为 \(H(i-1,j-1)\)。根据容斥原理，紫色矩形被减了两次。

• 一个 \((l_x, l_y)\) 到 \((r_x, r_y)\) 的子矩阵的 Hash 值为：
  

\[H(r_x,r_y)-H(l_x-1,r_y)p_x^{r_x-l_x+1}-H(r_x,l_y-1)p_y^{r_y-l_y+1}+H(r_x-1)(r_y-1)p_x^{r_x-l_x+1}p_y^{r_y-l_y+1}\]

解释： 如上图，紫色的矩形右下角为 \(H(r_x,l_y-1)\)，绿色的矩形右下角为 \(H(l_x-1,r_y)\)，它们重合部分的黄色矩形右下角为 \(H(l_x-1,l_y-1)\)。黑框矩形右下角为 \(H(r_x-1,r_y-1)\)。根据容斥原理，黄色矩形被减了两次。依然是容斥原理。
其中，\(p_x, p_y\) 是两个不相等却相近的质数。如果手动取模 \(mod\) 要保证取同一个值。
例题

Matrix Matcher

问题：\(T\) 组数据，每组数据给定一个 \(N\times M\) 的 \(A\) 矩阵和一个 \(X\times Y\) 的 \(B\) 矩阵求 \(B\) 矩阵在 \(A\) 矩阵中出现的次数。
[code]#include using namespace std;typedef unsigned long long ull;const int N = 1e3 + 8, px = 131, py = 137;int n, m, x, y, ans, T;ull pxpow[N], pypow[N], ahs[N][N], bhs[N][N];ull geths(ull h[][N], int lx, int ly, int rx, int ry) {    return h[rx][ry] - h[lx - 1][ry] * pxpow[rx - lx + 1] - h[rx][ly - 1] * pypow[ry - ly + 1]    + h[lx - 1][ly - 1] * pxpow[rx - lx + 1] * pypow[ry - ly + 1];}int main() {    pxpow[0] = pypow[0] = 1;    for (int i = 1; i < N; i++) pxpow = pxpow[i - 1] * px, pypow = pypow[i - 1] * py;    cin >> T;    while (T--) {        cin >> n >> m;        for (int i = 1; i  c;                ahs[j] = ahs[i - 1][j] * px + ahs[j - 1] * py - ahs[i - 1][j - 1] * px * py + c;            }        cin >> x >> y;        for (int i = 1; i  c;                bhs[j] = bhs[i - 1][j] * px + bhs[j - 1] * py - bhs[i - 1][j - 1] * px * py + c;            }        ans = 0;        for (int i = 1; i  m;    for (int i = 1; i  a[j];    for (int i = 1; i  1;                if (check(i - mid + 1, j - mid + 1, i + mid, j + mid)) l = mid;                else r = mid - 1;            }            ans += l;        }    cout > n;    for (int i = 1; i  x;            ahs[j] = ahs[i - 1][j] * px + ahs[j - 1] * py - ahs[i - 1][j - 1] * px * py + x;        }    for (int i = 1; i  x;            bhs[j] = bhs[i - 1][j] * px + bhs[j - 1] * py - bhs[i - 1][j - 1] * px * py + x;        }    for (int k = 1; k

分享、互助 让互联网精神温暖你我

新版吗？好像是停更了吧。