Number of Unique Arrays
Given
n arrays each one having a length l (l integers), you are asked to calculate the number of unique arrays. The arrays are considered unique if they differ in at least one element.Notice that comparing arrays one by one might take too long. You can hash an array with some hash function of your choice and try to compare the hashed values.
After that, you can take a large array of size
m and fill it with zeros. Every time you obtain a hash, you can mark that location in the array with one. In the end, you can compute the number of ones in the array.Note that the hash function should be taken modulo
m so that the indices take the range [0; m).Input
The first line of the input contains two integers
n (1 ≤ n ≤ 1000) and l (1 ≤ l ≤ 1000).The next
n lines contain l space-separated integers (0 ≤ ≤ ).Output
The program should print the number of unique arrays.
Examples
Input | Output |
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
If the hash function is not good enough and there are still collisions, try comparing it with 2 different hash functions - this makes the algorithm twice more robust to collisions.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB