Numero di Array Unici
Dato n array, ciascuno di lunghezza l (ovvero l interi), si richiede di calcolare quanti di questi array sono unici. Due array si considerano unici se differiscono almeno in un elemento.
Tuttavia, confrontare gli array uno a uno potrebbe richiedere troppo tempo. Un approccio alternativo consiste nell’applicare una funzione di hash (a scelta) a ogni array e poi confrontare i valori hash.
Dopo aver calcolato l’hash di un array, è possibile prendere un grande array di dimensione m e inizializzarlo a zero. Ogni volta che si ricava un hash, si “segna” (imposta a 1) la posizione corrispondente in questo grande array. Al termine, per scoprire quanti array diversi si sono incontrati, sarà sufficiente contare i valori pari a 1 in quest’ultimo array.
È importante notare che la funzione di hash deve essere utilizzata in modulo m, così che gli indici rientrino nell’intervallo [0; m).
Dati in Ingresso
La prima riga dell’input contiene due interi n (1 ≤ n ≤ 1000) e l (1 ≤ l ≤ 1000).
Le successive n righe contengono l interi separati da uno spazio (0 ≤ ≤ ).
Risultato
Il programma deve stampare il numero di array unici.
Esempi
Input | Output |
|---|---|
4 3 | 3 |
2 3 | 1 |
Suggerimento
Se la funzione di hash non è abbastanza efficace e si verificano ancora collisioni, prova a confrontare i risultati ottenuti con 2 funzioni di hash diverse: in questo modo l’algoritmo risulta due volte più robusto alle collisioni.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB