Количество уникальных массивов
Дано
n массивов, каждый из которых имеет длину l (по l целых чисел). Необходимо найти, сколько среди них уникальных. Массивы считаются уникальными, если они отличаются хотя бы одним элементом.Обратите внимание, что сравнивать массивы напрямую может быть слишком долго. Вместо этого можно использовать любую удобную хеш-функцию и сравнивать хеши.
Затем можно взять большой массив размером
m и заполнить его нулями. Каждый раз, когда получается очередной хеш, помечать соответствующую позицию в этом массиве единицей. В конце достаточно будет посчитать, сколько единиц содержится в этом большом массиве.Помните, что при вычислении хеша важно брать значение по модулю
m, чтобы полученные индексы попадали в диапазон [0; m).Ввод
В первой строке содержатся два целых числа
n (1 ≤ n ≤ 1000) и l (1 ≤ l ≤ 1000).В следующих
n строках приведены l целых чисел, разделённых пробелом (0 ≤ ≤ ).Вывод
Программа должна вывести количество уникальных массивов.
Примеры
Ввод | Вывод |
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 |
Подсказка
Если выбранная хеш-функция не обеспечивает достаточной надёжности и возникают коллизии, попробуйте использовать две разные хеш-функции. В этом случае алгоритм станет вдвое устойчивее к коллизиям.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB