---
tags: Hash, Matrix Hash, Multi Hash, Multi Matrix Hash, DP, Template, Partial Sum, DP
---

SPyofgame Matrix Hash Template
===

[link](link)

-----

###### Tags: Matrix Hash, Multi Matrix Hash, Partial Sum, DP

-----
### Mục tiêu

- Phiên bản static offline
- Offset $1, 1$ - Ô đầu ở $(1, 1)$ kết thúc $(n, m)$
- Tiền xử lí $init(c[][], n, m)$ trong $O(n \times m)$ thưc hiện xây dựng mảng hash trên ma trận $c[][]$ từ góc trái trên $(1, 1)$ đến góc phải dưới $(n, m)$
- Truy vấn $query(x, y, u, v)$ trong $O(1)$ cho biết giá trị hash của ma trận có góc trái trên $(x, y)$ và góc phải dưới $(u, v)$

-----
### Hằng số

Với $k$ là giá trị lớn nhất trong $c[][]$
- $ROWLIM > n$ là max độ dài hàng.
- $COLLIM > m$ là max độ dài cột.
- $ROWBASE > k$ là hằng số hash trên hàng.
- $COLBASE > k$ là hằng số hash trên cột.
- $MODULO$ > 1 là hằng số modulo của mã Hash.

Hash đạt hiêu quả nhất khi
- $ROWBASE > k + 1$
- $COLBASE > k + 1$
- $ROWBASE \neq COLBASE$
- $MODULO \approx 10^9$ và nguyên tố

-----
### Hướng dẫn

Tương tư như Hash trên một xâu, ta sẽ biểu diễn giá trị dưới dạng đa thức
- Ta định nghĩa $V[x][y]$ là giá trị hash tại ô $[x][y]$
- Ta có $V[x][y] = c[x][y] \times p^x \times q^y$

Với một bảng:

[_][_][_][_]
[_][a][b][c]
[_][d][e][f]
[_][g][h][i]

Khi ta hash ta sẽ mong nó ra giá trị như thế này

[a * p^0 * q^0][b * p^0 * q^1][c * p^0 * q^2]
[d * p^1 * q^0][e * p^1 * q^1][f * p^1 * q^2]
[g * p^2 * q^0][h * p^2 * q^1][i * p^2 * q^2]

hay

:::info
$a \times 1 \qquad \ \ \ b \times q \qquad \ \ \ c \times q^2$
$d \times p \qquad \ \ e \times pq \qquad \ f \times pq^2$
$g \times p^2 \qquad h \times p^2q \qquad i \times p^2q^2$
:::

Để tính truy vấn trên một hình chữ nhật bất kì trong $O(1)$ ta sử dụng ý tưởng của mảng cộng dồn.
- Ta định nghĩa $H[x][y]$ là giá trị hash của ma trận góc trái trên $[1][1]$ và góc phải dưới $[x][y]$
- Với $x = 0$ ta có $H[0][y] = 0\ \forall\ y \geq 0$
- Với $y = 0$ ta có $H[x][0] = 0\ \forall\ x \geq 0$
- Ngược lại ta có $H[x][y] = \overset{x}{\underset{p = 1}{\Large \Sigma}} \overset{y}{\underset{q = 1}{\Large \Sigma}} V[x][y] = P[x][y] + H[x - 1][y] \times p + H[x][y - 1] \times q - H[x-1][y-1] \times pq$

Lúc này truy vấn một ma trận góc trái trên $(x, y)$ và góc phải dưới $(u, v)$ được tính như sau
- $Q = H[u][v] - H[x - 1][v] \times p^{u-x+1} - H[u][y - 1] \times q^{v-y+1} + H[x-1][y-1] \times p^{u-x+1} \times q^{v-y+1}$

-----
### Hash Code

> **Declared Time:** $O(ROWLIM \times COLLIM)$
> **Declared Space:** $O(ROWLIM \times COLLIM)$
> **Precalculation Time:** $O(n \times m)$
> **Precalculation Space:** $O(n \times m)$
> **Query Time:** $O(1)$
> **Query Space:** $O(1)$
> **Accuracy:** Quite High
> **Constant:** High
> **Algo:** Matrix Hash, Partial Sum, DP

template<const int ROWLIM, const int COLLIM, const int ROWBASE, const int COLBASE, const int MODULO>
struct Matrix_Hash
{
    /// For convenient
    const int ROWCOL = (1LL * ROWBASE * COLBASE) % MODULO;

    int R[ROWLIM]; /// ROWBASE ^ N % MODULO
    int C[COLLIM]; /// COLBASE ^ M % MODULO
    int H[ROWLIM][COLLIM]; /// Hashtable

    /// Initialize this hash
    void init(const vector<vector<char> > &c, int n, int m)
    {
        /// Calculate Rowbase Modulo Power
        R[0] = 1;
        for (int i = 1; i < ROWLIM; ++i)
            R[i] = (1LL * R[i - 1] * ROWBASE) % MODULO;

        /// Calculate Colbase Modulo Power
        C[0] = 1;
        for (int j = 1; j < COLLIM; ++j)
            C[j] = (1LL * C[j - 1] * COLBASE) % MODULO;

        /// Calculate 2D Hash
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                H[i][j] = (         c[i][j]               + 1LL * H[i - 1][j]     * COLBASE
                            + 1LL * H[i][j - 1] * ROWBASE - 1LL * H[i - 1][j - 1] * ROWCOL ) % MODULO;
                            
                if (H[i][j] < 0) H[i][j] += MODULO;
            }
        }
    }

    /// Matrix Hash [x, y] -> [u, v] inclusive
    int query(int x, int y, int u, int v)
    {
        int XY = (1LL * C[u - x + 1] * R[v - y + 1]) % MODULO;
        int res = (			H[u][v] 				   - 1LL * H[x - 1][v]     * C[u - x + 1]
                    - 1LL * H[u][y - 1] * R[v - y + 1] + 1LL * H[x - 1][y - 1] *      XY     ) % MODULO;
                    
        if (res < 0) res += MODULO;
        return res;   
    }
};

Hash<1010, 1010, 1234, 123456789, 1000000007> H;

-----
### Struct-free Hash Code

> **Declared Time:** $O(ROWLIM \times COLLIM)$
> **Declared Space:** $O(ROWLIM \times COLLIM)$
> **Precalculation Time:** $O(n \times m)$
> **Precalculation Space:** $O(n \times m)$
> **Query Time:** $O(1)$
> **Query Space:** $O(1)$
> **Accuracy:** Quite High
> **Constant:** Quite High
> **Algo:** Matrix Hash, Partial Sum, DP

char c[ROWLIM][COLLIM];
int R[ROWLIM]; /// ROWBASE ^ N % MODULO
int C[COLLIM]; /// COLBASE ^ M % MODULO
int H[ROWLIM][COLLIM]; /// Hashtable

/// Initialize this hash
void init(int n, int m)
{
    /// Calculate Rowbase Modulo Power
    R[0] = 1;
    for (int i = 1; i < LIM; ++i)
        R[i] = (1LL * R[i - 1] * ROWBASE) % MODULO;

    /// Calculate Colbase Modulo Power
    C[0] = 1;
    for (int j = 1; j < LIM; ++j)
        C[j] = (1LL * C[j - 1] * COLBASE) % MODULO;

    /// Calculate 2D Hash
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            H[i][j] = (         c[i][j]             + 1LL * H[i - 1][j]     * COLBASE
                        + 1LL * H[i][j - 1] * ROWBASE - 1LL * H[i - 1][j - 1] * ROWCOL ) % MODULO;
                        
            if (H[i][j] < 0) H[i][j] += MODULO;
        }
    }
}

/// 2D Hash [x, y] -> [u, v]
int query(int x, int y, int u, int v)
{
    int XY = (1LL * C[u - x + 1] * R[v - y + 1]) % MODULO;
    int res = (			H[u][v] 				 - 1LL * H[x - 1][v]     * C[u - x + 1]
                - 1LL * H[u][y - 1] * R[v - y + 1] + 1LL * H[x - 1][y - 1] * XY          ) % MODULO;
                
    if (res < 0) res += MODULO;
    return res;   
}

-----
### Multi Hash Code

> For $K =$ number of hashes
> **Declared Time:** $O(ROWLIM \times COLLIM)$
> **Declared Space:** $O(ROWLIM \times COLLIM)$
> **Precalculation Time:** $O(n \times m)$
> **Precalculation Space:** $O(n \times m)$
> **Query Time:** $O(1)$
> **Query Space:** $O(1)$
> **Accuracy:** Significantly higher for larger $K$
> **Constant:** Very High $c_0 = K \times c$
> **Algo:** Matrix Hash, Partial Sum, DP

template<const int ROWLIM, const int COLLIM, const int ROWBASE, const int COLBASE, const int MODULO>
struct Matrix_Hash
{
    /// For convenient
    const int ROWCOL = (1LL * ROWBASE * COLBASE) % MODULO;

    int R[ROWLIM]; /// ROWBASE ^ N % MODULO
    int C[COLLIM]; /// COLBASE ^ M % MODULO
    int H[ROWLIM][COLLIM]; /// Hashtable

    /// Initialize this hash
    void init(const vector<vector<char> > &c, int n, int m)
    {
        /// Calculate Rowbase Modulo Power
        R[0] = 1;
        for (int i = 1; i < ROWLIM; ++i)
            R[i] = (1LL * R[i - 1] * ROWBASE) % MODULO;

        /// Calculate Colbase Modulo Power
        C[0] = 1;
        for (int j = 1; j < COLLIM; ++j)
            C[j] = (1LL * C[j - 1] * COLBASE) % MODULO;

        /// Calculate 2D Hash
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                H[i][j] = (         c[i][j]               + 1LL * H[i - 1][j]     * COLBASE
                            + 1LL * H[i][j - 1] * ROWBASE - 1LL * H[i - 1][j - 1] * ROWCOL ) % MODULO;
                            
                if (H[i][j] < 0) H[i][j] += MODULO;
            }
        }
    }

    /// Matrix Hash [x, y] -> [u, v] inclusive
    int query(int x, int y, int u, int v)
    {
        int XY = (1LL * C[u - x + 1] * R[v - y + 1]) % MODULO;
        int res = (			H[u][v] 				   - 1LL * H[x - 1][v]     * C[u - x + 1]
                    - 1LL * H[u][y - 1] * R[v - y + 1] + 1LL * H[x - 1][y - 1] *      XY     ) % MODULO;
                    
        if (res < 0) res += MODULO;
        return res;   
    }
};

/// Hexa-Hashes Value
typedef tuple<int, int, int, int, int, int> Pack;
struct Multi_Matrix_Hash
{
    Matrix_Hash<LIM, LIM, 1234, 123456789, 1000000007> A;
    Matrix_Hash<LIM, LIM, 12345, 12345678, 1000000009> B;
    Matrix_Hash<LIM, LIM, 123456, 1234567, 1000000021> C;
    Matrix_Hash<LIM, LIM, 1234567, 123456, 1000000033> D;
    Matrix_Hash<LIM, LIM, 12345678, 12345, 1000000087> E;
    Matrix_Hash<LIM, LIM, 123456789, 1234, 1000000093> F;
    
    /// Initialize these hashes
    void init(const vector<vector<char> > &c, int n, int m)
    {
        A.init(c, n, m);
        B.init(c, n, m);
        C.init(c, n, m);
        D.init(c, n, m);
        E.init(c, n, m);
        F.init(c, n, m);
    }

    /// Multi Matrix Hash [x, y] -> [u, v] inclusive
    Pack query(int x, int y, int u, int v)
    {
        return Pack {
            A.query(x, y, u, v),
            B.query(x, y, u, v),
            C.query(x, y, u, v),
            D.query(x, y, u, v),
            E.query(x, y, u, v),
            F.query(x, y, u, v)
        };
    }
};