13. Пароли
В корпорации Crazel (Crazy Electronics) исследуют возможность использования процессоров, работающих на системах счисления с различными основаниями. В разрабатываемом процессоре элементарной ячейкой памяти является крабайт (crabyte). Крабайт состоит из Q крабит (crabit). Каждый крабит может принимать значения от 0 до P-1, где P – простое число. Таким образом, один крабайт памяти может хранить целые числа в диапазоне от 0 до P^Q-1 включительно.
Арифметика на подобном процессоре выполняется по модулю P^Q. При сложении или умножении двух крабайтовых чисел в ячейку результата записывается лишь остаток от деления на P^Q.
Джордж — гений, работающий в корпорации Crazel. Как и все гении, он очень рассеян, и вообще человек не от мира сего. В частности, его мозг работает специфически. Например, он всегда вспоминает необходимые пароли, но обычно не с первой попытки. А на некоторых сайтах после тр?х неудачных попыток ввода пароля аккаунт блокируется. Чтобы избежать подобных проблем, он решил сохранять хеши от паролей в памяти прототипа разрабатываемого процессора. Для этого он записал пароль в память процессора, а затем запустил собственную программу, которая вычисляет хеш пароля по следующей формуле:
Xj – содержимое j-го крабайта пароля,
Yi – содержимое i-го крабайта результирующего хеша,
Aij – записанный в крабайте элемент фиксированной матрицы.
Майкл хочет украсть один из паролей Джорджа. Он узнал хеш, записанный в памяти прототипа, а также матрицу, используемую программой Джорджа. Он просит вас помочь ему в осуществлении коварного плана.
Найдите количество паролей, имеющий заданный хеш, а также выведите любой из них.
Входные данные
В первой строке входного файла записано четыре целых числа: N – длина пароля в крабайтах, M – длина хеша в крабайтах (1 <= N, M <= 200), P – количество возможных состояний крабита (2 <= P <<= 109) и Q – количество крабит в крабайте (1 <= Q <= 30). В следующей строке записано M чисел – содержимое крабайтов хеша. Затем ид?т M строк по N чисел в каждой – матрица, заложенная в программу Джорджа.
Гарантируется, что P – простое число. Чтобы было проще эмулировать работу прототипа на обычном 32-битном процессоре, количество возможных состояний крабайта не превосходит 10^9.
Выходные данные
Первая строка выходного файла должна содержать информацию о количестве паролей, имеющих заданный хеш. Если таких паролей нет, выведите слово Fool. Если паролей менее миллиарда, то выведите слово Little и количество паролей через пробел. Если паролей не меньше миллиарда, то выведите Many и остаток от деления количества паролей на (10^9 + 7) через пробел.
В случае, когда искомые пароли существуют, выведите во вторую строку N чисел через пробел – содержимое крабайт любого из этих паролей.
Примеры
input.txt
5 2 7 1
3 3
1 1 1 1 1
2 2 2 2 2
output.txt
Fool
input.txt
2 3 5 2
3 6 12
1 1
2 2
4 4
output.txt
Little 25
3 0
input.txt
5 5 2 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
output.txt
Many 898961331
2 3 5 7 11
Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru
| 