Número de Arrays Únicos
Dado que existem
n arrays, cada um com comprimento l (l inteiros), pretende-se calcular o número de arrays únicos. Considera-se que dois arrays são diferentes se divergirem em pelo menos um elemento.Note que comparar os arrays individualmente pode demorar demasiado. Para evitar esse problema, pode recorrer-se a uma função de hash à sua escolha e comparar apenas os valores resultantes dessa função.
Depois disso, pode-se pegar num array grande de tamanho
m e inicializá-lo a zeros. De cada vez que se obtiver um valor de hash, marca-se essa posição no array com 1. No final, é possível contar quantas posições ficaram a 1.Note que a função de hash deve ser calculada módulo
m, de forma a garantir que os índices ficam no intervalo [0; m).Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ 1000) e l (1 ≤ l ≤ 1000).As próximas
n linhas contêm l inteiros separados por espaços (0 ≤ ≤ ).Saída
O programa deve imprimir o número de arrays únicos.
Exemplos
Entrada | Saída |
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
Se a função de hash não for suficientemente boa e ainda ocorrerem colisões, experimente usar 2 funções de hash diferentes – isto torna o algoritmo duas vezes mais resistente a colisões.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB