Número de Arreglos Únicos
Dadas
n arreglos, cada uno con longitud l (l enteros), se te pide calcular la cantidad de arreglos únicos. Los arreglos se consideran únicos si difieren al menos en un elemento.Ten en cuenta que comparar los arreglos uno por uno podría tomar demasiado tiempo. Puedes aplicar un hash a cada arreglo usando alguna función de hash de tu elección y así comparar los valores resultantes.
Después, puedes tomar un arreglo grande de tamaño
m y llenarlo con ceros. Cada vez que obtengas un hash, marcas esa posición en el arreglo con un uno. Al final, podrás calcular cuántos unos hay en el arreglo.Ten en cuenta que la función de hash se debe tomar módulo
m para que los índices estén en el rango [0, m).Entrada
La primera línea de la entrada contiene dos enteros
n (1 ≤ n ≤ 1000) y l (1 ≤ l ≤ 1000).Las siguientes
n líneas contienen l enteros separados por espacios (0 ≤ ≤ ).Salida
El programa debe imprimir el número de arreglos únicos.
Ejemplos
Entrada | Salida |
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 función de hash no es lo suficientemente buena y aún se producen colisiones, trata de compararlas con 2 funciones de hash diferentes. Esto hace que el algoritmo sea el doble de robusto ante colisiones.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB