Try   HackMD

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

SPyofgame Matrix Hash Template

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×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
  • ROWBASECOLBASE
  • MODULO109
    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]×px×qy

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

a×1   b×q   c×q2
d×p  e×pq f×pq2

g×p2h×p2qi×p2q2

Để 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  y0
  • Với
    y=0
    ta có
    H[x][0]=0  x0
  • Ngược lại ta có
    H[x][y]=Σp=1xΣq=1yV[x][y]=P[x][y]+H[x1][y]×p+H[x][y1]×qH[x1][y1]×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[x1][v]×pux+1H[u][y1]×qvy+1+H[x1][y1]×pux+1×qvy+1

Hash Code

Declared Time:

O(ROWLIM×COLLIM)
Declared Space:
O(ROWLIM×COLLIM)

Precalculation Time:
O(n×m)

Precalculation Space:
O(n×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×COLLIM)
Declared Space:
O(ROWLIM×COLLIM)

Precalculation Time:
O(n×m)

Precalculation Space:
O(n×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×COLLIM)

Declared Space:
O(ROWLIM×COLLIM)

Precalculation Time:
O(n×m)

Precalculation Space:
O(n×m)

Query Time:
O(1)

Query Space:
O(1)

Accuracy: Significantly higher for larger
K

Constant: Very High
c0=K×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) }; } };