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

SPyofgame Matrix Hash Template

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í
$i n i t (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
$q u e r y (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 [] []

$R O W L I M > n$ là max độ dài hàng.
$C O L L I M > m$ là max độ dài cột.
$R O W B A S E > k$ là hằng số hash trên hàng.
$C O L B A S E > k$ là hằng số hash trên cột.
$M O D U L O$ > 1 là hằng số modulo của mã Hash.

Hash đạt hiêu quả nhất khi

$R O W B A S E > k + 1$
$C O L B A S E > k + 1$
$R O W B A S E \neq C O L B A S E$
$M O D U L O \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

a \times 1 b \times q c \times q^{2}

d \times p e \times p q f \times p q^{2}

g \times p^{2} h \times p^{2} q i \times p^{2} q^{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}{Σ}} \overset{y}{\underset{q = 1}{Σ}} V [x] [y] = P [x] [y] + H [x - 1] [y] \times p + H [x] [y - 1] \times q - H [x - 1] [y - 1] \times p q$

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 (R O W L I M \times C O L L I M)$
Declared Space:
$O (R O W L I M \times C O L L I M)$
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 (R O W L I M \times C O L L I M)$
Declared Space:
$O (R O W L I M \times C O L L I M)$
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 (R O W L I M \times C O L L I M)$
Declared Space:
$O (R O W L I M \times C O L L I M)$
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)
        };
    }
};

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

SPyofgame Matrix Hash Template

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

Mục tiêu

Hằng số

Hướng dẫn

Hash Code

Struct-free Hash Code

Multi Hash Code

Read more

Hello

AISearch

AMSIT, Homework

Practice VNOI2 Log