Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Хеш-функция

(Время: 2 сек. Память: 16 Мб Сложность: 37%)

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

Пусть дана строка S = s1s2 … sl, состоящая из цифр от 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(1), S(2), … , S(n)), каждая из которых состоит только из цифр от 0 до 9, и числа m и x. Необходимо найти количество таких пар (i, j), где 1 <= i, j <= n, i < j, что p(S(i), x, m) = p(S(j), x, m).

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
18 3 8
1234
239
366
261
32890
43823490
382390
3043840
11
25 10 100
1
2
3
4
5
0

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483