# KỸ THUẬT HASH BẰNG NGHỊCH ĐẢO MODULO

**1. Cài đặt hash [1, n]**

- Gọi powBase[i] là mũ base từ 0 đến n - 1 (n = s.size()).

const long long mod = 1e9 + 7;
const int base = 311; //Thường base là snt
//Tính powBase
powBase[0] = 1; //base^0 = 1
for(int i = 0; i < n; i++){
    powBase[i] = (1LL * powBase[i - 1] * base) % mod;
}

//Tính hash 1 -> n
hash[0] = s[0] - 'a' + 1; // '+1' lên để tránh TH s[0] - 'a' = 0 thì lúc đó sẽ gây cản trở việc tính hash sau này
for(int i = 1; i <= n; i++){
    hash[i] = hash[i - 1] + 1LL * (s[i] - 'a' + 1) * powBase[i]; 
}

**2. Lấy hash trong [L, R]**
- Ta có công thức như sau:


- Cách chứng minh (bằng cách thế số):

VD: Ta có dãy số dưới và cần tính đoạn [5, 6], thì ta có cách làm:

Tuy nhiên, khi quay lại công thức trên, ta để ý rằng công thức không để dạng chia bởi vì không có modulo nào cho phép chia cả. Nhưng bài toán vẫn chưa dừng lại ở đây, ta cần phải tính (base^L^)^-1^ % p, và ta sẽ giải quyết vấn đề đó ở phần tiếp theo.

**3. Xử lí phần modulo**
- Theo định lý fermat nhỏ thì: a^p-1^ ≡ 1 (mod p), p là số nguyên tố và a không chia hết cho p (Phần chứng minh ở dưới cùng).

Từ công thức trên ta biến đổi:
Vì p là hằng số rất lớn nên ta không cần lo p - 2 < 0.
Từ đó, ta hãy coi (base^L^)^-1^ chính là a^-1^ và từ đó ta chỉ cần tính a^p-2^ là xong.
- Code tính a^b^ trong O(log~2~b):

     long long ans;
     const long long p = 1e9 + 7;
     long long inversePow(long long a, long long b){
         if(b == 0) return 1; //a mu 0 = 1
         long long cur = inversePow(a, b / 2);
         cur = (cur % p * cur % p) % p;
         if(b % 2 != 0) cur = (cur * a) % p;
         return ans = cur;
     }

- Và ta có code tìm hash [L, R] hoàn chỉnh như sau:

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll powBase[1000005], pre[100005], pre2[100005];
    string s, t;
    const long long p = 1e9 + 7;
    const int base = 311; // Base thường sẽ là snt, cụ thể  là 311 hay 31

    // Tính modulo đảo
    long long inversePow(long long a, long long b) {
        if (b == 0) return 1; // a mu 0 = 1
        long long cur = inversePow(a, b / 2);
        cur = (cur % p * cur % p) % p;
        if (b % 2 != 0) cur = (cur * a) % p;
        return cur;
    }

    // Tính hash L - R
    // Hash [L, R] xâu S
    long long getHashS(int L, int R) {
        return (pre[R] - pre[L - 1]) % p * inversePow(1LL * powBase[L], p - 2) % p;
    }

    // Hash [L, R] xâu T
    long long getHashT(int L, int R) {
        return (pre2[R] - pre2[L - 1]) % p * inversePow(1LL * powBase[L], p - 2) % p;
    }

    int main() {
        cin >> s >> t;
        int n = max(s.size(), t.size());
        s = ' ' + s;
        t = ' ' + t; // 1-based index

        // Tính base^i;
        powBase[0] = 1; // base^0 = 1
        for (int i = 1; i <= n; i++) {
            powBase[i] = (1LL * powBase[i - 1] * base) % p;
        }

        // Tính hash 1 -> n
        pre[0] = s[0] - 'a' + 1;
        pre2[0] = t[0] - 'a' + 1;

        // hash xâu s
        for (int i = 1; i < 1LL * s.size(); i++) {
            pre[i] = pre[i - 1] + 1LL * (s[i] - 'a' + 1) * powBase[i];
        }

        // hash xâu t
        for (int i = 1; i < 1LL * t.size(); i++) {
            pre2[i] = pre2[i - 1] + 1LL * (t[i] - 'a' + 1) * powBase[i];
        }

        // Lấy hash L - R
        cout << getHashS(4, 5) << " " << getHashT(2, 3);
    }

    
**4 Optimize code**
- Tuy nhiên, để optimize code trên thì ta dùng thêm mảng invBase[i] là modulo nghịch đảo của basePow[i]. Code từ O(Q * log~2~p) xuống còn O(Q + log~2~p) với Q là số truy vấn.
- Nhận xét rằng:
    
    inv[N] = base^-N^ . base^0^ 
    
    inv[N - 1] = base^-N^ . base^1^ = inv[N] * base
    
    inv[N - 2] = base^-N^ . base^2^ = inv[N - 1] * base
    
    inv[N - 3] = base^-N^ . base^3^ = int[N - 2] * base
    
    Qua đó ý tưởng sẽ là chạy vòng lặp i ∈ [n - 1, 0] để tính invBase[i]
- Code hoàn chỉnh (optimized):

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll powBase[1000005], pre[100005], pre2[100005], invPow[100005];
string s, t;
const long long p = 1e9 + 7;
const int base = 311; // Base thường sẽ là snt, cụ thể là 311 hay 31

// Tính modulo đảo
long long inversePow(long long a, long long b) {
if (b == 0) return 1; // a mu 0 = 1
long long cur = inversePow(a, b / 2);
cur = (cur % p * cur % p) % p;
if (b % 2 != 0) cur = (cur * a) % p;
return cur;
}

// Tính hash L - R
// Hash [L, R] xâu S
long long getHashS(int L, int R) {
return ((pre[R] - pre[L - 1]) * invPow[L]) % p;
}

// Hash [L, R] xâu T
long long getHashT(int L, int R) {
return ((pre2[R] - pre2[L - 1]) * invPow[L]) % p;
}

int main() {
cin >> s >> t;
int n = max(t.size(), s.size());
s = ' ' + s;
t = ' ' + t; // 1-based index

// Tính base^i
powBase[0] = 1; // base^0 = 1
for (int i = 1; i <= n; i++) {
powBase[i] = (1LL * powBase[i - 1] * base) % p;
}

//Tính Inverse Base^i

invPow[n] = inversePow(powBase[n], p - 2);
for(int i = n - 1; i >= 0; i--) invPow[i] = (invPow[i + 1] * base) % p;

// Tính hash 1 -> n
pre[0] = s[0] - 'a' + 1;
pre2[0] = t[0] - 'a' + 1;

// hash xâu s
for (int i = 1; i < 1LL * s.size(); i++) {
pre[i] = pre[i - 1] + 1LL * (s[i] - 'a' + 1) * powBase[i];
}

// hash xâu t
for (int i = 1; i < 1LL * t.size(); i++) {
pre2[i] = pre2[i - 1] + 1LL * (t[i] - 'a' + 1) * powBase[i];
}

// Lấy hash L - R
cout << getHashT(2, 3) << " " << getHashS(4, 5);
}

==Vì sao không chạy từ 1 đến n mà là n - 1 về 0:==

Quan sát được:

inv[0] = 1.

inv[1] = inv[0] : base = base^-1^ = inversePow(base, p - 2) = base^p-2^ mod p.

inv[2] = inv[1] : base.

inv[3] = inv[2] : base.

inv[4] = inv[3] : base.


Nhưng trong quá trình tính ta cần lấy modulo nữa nhưng modulo thì không dùng cho phép chia được nên ta bát bỏ ý tưởng trên.

    
:::info 
Chứng minh định lý Fermat nhỏ:
https://hackmd.io/@c3jv2tKJQeqHkvfbGE2CSA/chungminhdinhliFermatnho
:::