Nombre de tableaux uniques
Étant donné
n tableaux, chacun ayant une longueur l (soit l entiers), vous devez déterminer le nombre de tableaux uniques. Deux tableaux sont considérés uniques s’ils diffèrent par au moins un élément.Notez que comparer les tableaux un par un peut prendre trop de temps. Vous pouvez plutôt calculer un hachage (hash) pour chaque tableau en utilisant une fonction de hachage de votre choix, puis comparer leurs valeurs de hachage.
Ensuite, vous pouvez réserver un grand tableau de taille
m et l’initialiser avec des zéros. Chaque fois que vous calculez un hachage, vous marquez l’index correspondant dans ce grand tableau en y plaçant la valeur 1. À la fin, il vous suffit de compter combien de cases contiennent la valeur 1.Gardez à l’esprit que la fonction de hachage doit être calculée modulo
m afin que les indices restent dans l’intervalle [0 ; m).Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ 1000) et l (1 ≤ l ≤ 1000).Les
n lignes suivantes contiennent chacune l entiers séparés par des espaces (0 ≤ ≤ ).Sortie
Le programme doit afficher le nombre de tableaux uniques.
Exemples
Entrée | Sortie |
4 3
1 2 3
3 2 1
2 5 3
3 2 1 | 3 |
2 3
1 2 3 4
1 2 3 4 | 1 |
Hint
Si la fonction de hachage n’est pas assez performante et qu’il y a encore des collisions, essayez d’utiliser 2 fonctions de hachage différentes : cela rend l’algorithme deux fois plus robuste face aux collisions.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB