SPyofgame Matrix Hash Template
link
Mục tiêu
- Phiên bản static offline
- Offset - Ô đầu ở kết thúc
- Tiền xử lí trong thưc hiện xây dựng mảng hash trên ma trận từ góc trái trên đến góc phải dưới
- Truy vấn trong cho biết giá trị hash của ma trận có góc trái trên và góc phải dưới
Hằng số
Với là giá trị lớn nhất trong
- là max độ dài hàng.
- là max độ dài cột.
- là hằng số hash trên hàng.
- là hằng số hash trên cột.
- > 1 là hằng số modulo của mã Hash.
Hash đạt hiêu quả nhất khi
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 là giá trị hash tại ô
- Ta có
Với một bảng:
Khi ta hash ta sẽ mong nó ra giá trị như thế này
hay
Để tính truy vấn trên một hình chữ nhật bất kì trong ta sử dụng ý tưởng của mảng cộng dồn.
- Ta định nghĩa là giá trị hash của ma trận góc trái trên và góc phải dưới
- Với ta có
- Với ta có
- Ngược lại ta có
Lúc này truy vấn một ma trận góc trái trên và góc phải dưới được tính như sau
Hash Code
Declared Time:
Declared Space:
Precalculation Time:
Precalculation Space:
Query Time:
Query Space:
Accuracy: Quite High
Constant: High
Algo: Matrix Hash, Partial Sum, DP
Struct-free Hash Code
Declared Time:
Declared Space:
Precalculation Time:
Precalculation Space:
Query Time:
Query Space:
Accuracy: Quite High
Constant: Quite High
Algo: Matrix Hash, Partial Sum, DP
Multi Hash Code
For number of hashes
Declared Time:
Declared Space:
Precalculation Time:
Precalculation Space:
Query Time:
Query Space:
Accuracy: Significantly higher for larger
Constant: Very 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
{
const int ROWCOL = (1LL * ROWBASE * COLBASE) % MODULO;
int R[ROWLIM];
int C[COLLIM];
int H[ROWLIM][COLLIM];
void init(const vector<vector<char> > &c, int n, int m)
{
R[0] = 1;
for (int i = 1; i < ROWLIM; ++i)
R[i] = (1LL * R[i - 1] * ROWBASE) % MODULO;
C[0] = 1;
for (int j = 1; j < COLLIM; ++j)
C[j] = (1LL * C[j - 1] * COLBASE) % MODULO;
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;
}
}
}
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;
}
};
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;
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);
}
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)
};
}
};