Invece di calcolare semplicemente l'hash di una sequenza, possiamo memorizzare il valore in ciascuno dei suoi prefissi. Si noti che questi saranno valori hash per sequenze uguali al prefisso corrispondente.
Con una tale struttura, puoi calcolare rapidamente il valore hash per qualsiasi sottosegmento di questa sequenza (simile alle somme dei prefissi).
Se vogliamo calcolare l'hash del sottosegmento [l;r], allora dobbiamo prendere l'hash sul prefisso r e sottrarre l'hash sul prefisso l-1 moltiplicato per p alla potenza di r-l+1. Perché è così diventa chiaro se scrivi i valori sui prefissi e vedi cosa succede. Spero che tu riesca a guardare questa foto.
Come risultato di tali azioni, otteniamo un hash di un sottosegmento della sequenza originale. Inoltre, questo hash è uguale a quello se fosse considerato come un hash da una sequenza uguale a questo sottosegmento (non sono necessarie ulteriori conversioni di gradi o simili per il confronto con altri valori).
Ci sono due punti da chiarire qui:
1) Per moltiplicare velocemente per p alla potenza r-l+1, è necessario precalcolare tutte le potenze possibili di p modulo mod.
2) Va ricordato che eseguiamo tutti i calcoli modulo modulo, e quindi potrebbe risultare che dopo aver sottratto gli hash del prefisso, otterremo un numero negativo. Per evitare ciò, puoi sempre aggiungere mod prima di sottrarre. Inoltre, non dimenticare di prendere il valore del modulo dopo le moltiplicazioni e tutte le addizioni.
Nel codice ha questo aspetto:
#include <bits/stdc++.h>
utilizzando lo spazio dei nomi std;
typedef long longll;
const int MAXN = 1000003;
// modulo base e hash
ll p, mod;
// prefisso hash ed esponenti p
h[MAXN], pots[MAXN];
// calcolo dell'hash del sottosegmento [l;r]
ll get_segment_hash(int l, int r) {
return (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod;
}
int principale()
{
// in qualche modo ottieni p e mod
// precalcola le potenze p
pot[0] = 1;
for (int i = 0; i < MAXN; i++)
pows[i] = (pows[i - 1] * p) % mod;
//
// soluzione del problema principale
//
ritorno 0;
}