Calcolando la modalità di successioni XOR

Question

Mi sono confrontato con questo problema in una sfida di programmazione online e da allora mi ha infastidito:

Nel problema, ti viene dato un elenco di numeri a 16 bit, diciamo $ a_0, a_1, ..., a_n $. Una "successione XOR" è definita come la combinazione esclusiva o di ogni elemento in una successione consecutiva dell'elenco. Il problema è che è necessario trovare la successione XOR che si verifica più comunemente da ogni possibile successione consecutiva nell'elenco. In caso di pareggio, il valore xor numerico più basso di quelli più frequentemente presenti.

La prima soluzione che mi è venuta in mente è stata una soluzione $ o (n^2) $ in cui calcolo Xor per successioni consecutive $ a_0, ..., a_i $ da $ i = 0 $ a $ i = n $, che può Essere fatto in $ O (n) $ e fare la stessa cosa a partire da $ A_1 $, ecc. E aumentando un contatore in una mappa per ogni risultato. So che questo ripete molto lavoro, quindi ho affrontato il problema da un angolo diverso e ho cercato di definirlo matematicamente. Ho definito $ x_ {i, j} $ per essere il xor di $ a_i, ..., a_j $ in modo da poter scrivere quanto segue:

$ X_ {i, j} = inizio {casi} a_i & text {if} i = j a_j oplus x_ {0, j-1} & text {if} i = 0 text {and} j> 0 x_ {0, i-1} oplus x_ {0, j} & text {if} 0 <i <j end {case} $

L'ho implementato con la memorizzazione, che credo elimina tutti i calcoli ridondanti, ma l'uso della memorizzazione risulta essere lenta e usare $ o (n^2) $ spazio quando si tenta di calcolare tutti $ x_ {i, j} $ per $ 0 leq i leq n $ e $ i leq j leq n $, che è inaccettabile.

C'è un modo per farlo più veloce di $ o (n^2) $? O in caso contrario, esiste un modo efficiente per ridurre il numero di calcoli? O mi manca una semplificazione al problema che non mi richiede di calcolare ogni $ x_ {i, j} $? Sono un po 'nuovo alla programmazione dinamica, quindi è stato difficile avvolgere il mio cervello attorno a questo problema. La mia soluzione originale è stata troppo lenta di un fattore di circa 5 secondi (rispetto al limite di tempo di 4 secondi per la sfida), quindi credo che anche una riduzione costante del fattore nel tempo renderebbe accettabile la soluzione.