Хеш-функция

В задачах поиска часто используются так называемые хеш-функции. Одним из важнейших классов хеш-функций являются так называемые полиномиальные хеш-функции.

Пусть дана строка S = s₁s₂ … s_l, состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функции p(S, x, m) вычисляется следующим образом:

(a mod b обозначает остаток от деления числа a на число b). Например, пусть S = 0123, тогда p(S, 2, 5) = (0 • 1 + 1 • 2 + 2 • 4 + 3 • 8) mod 5 = 4.

Вам даны множество из n строк (S⁽¹⁾, S⁽²⁾, … , S⁽ⁿ⁾), каждая из которых состоит только из цифр от 0 до 9, и числа m и x. Необходимо найти количество таких пар (i, j), где 1 ≤ i, j ≤ n, i < j, что p(S⁽ⁱ⁾, x, m) = p(S^(j), x, m).

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа: n (1 ≤ n ≤ 30000), m (1 ≤ m ≤ 2000), x (1 ≤ x ≤ 100). Далее идут n строк, каждая из которых содержит по одной строке из данного множества: 2-ая строка входного файла содержит S⁽¹⁾, 3-я - S⁽²⁾, . . . , (i + 1)-ая - S⁽ⁱ⁾, ... , (n + 1)-ая - S⁽ⁿ⁾. Длины S⁽ⁱ⁾ не превосходят 100, S⁽ⁱ⁾ не пусты и состоят только из цифр от 0 до 9.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]