Number of Unique Arrays
narrays each one having a length
lintegers), 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
mand 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
mso that the indices take the range [0; m).
The first line of the input contains two integers
n(1 ≤ n ≤ 1000) and
l(1 ≤ l ≤ 1000).
lspace-separated integers (0 ≤ ≤ ).
The program should print the number of unique arrays.
4 3 1 2 3 3 2 1 2 5 3 3 2 1
2 3 1 2 3 4 1 2 3 4
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.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB