Задача №114060. Кроссворд (Osmosmjerka)
Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(N \times M\)\(\), заполненный буквами и замостили им бесконечную плоскость. Например, прямоугольник
hsin
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
В данном кроссворде нами случайно (равновероятно) выбирается одна клетка и одно из восьми направлений. Затем начиная с данной клетки в данном направлении выписывается слово длины \(\)\(K\)\(\). Описанный процесс повторяется (независимо от первого раза) второй раз. Вам требуется вычислить вероятность того, что два выписанных слова совпадут.
Первая строка содержит три числа \(\)\(M, N, K\)\(\) (\(\)\(1 \leq N, M \leq 500\)\(\), \(\)\(1 \leq K \leq 10^9\)\(\)) — размеры блока и длина выбираемого слова соответственно.
Следующие \(\)\(M\)\(\) строк содержат по \(\)\(N\)\(\) латинских строчных букв, задавая блок, коим замощается доска. Гарантируется, что в данных есть хотя бы две различные буквы.
Выведите требуемую вероятность в виде сокращённой дроби «p/q» без пробелов и кавычек.
Решение, правильно работающее на тестах, в которых \(\)\(N = M\)\(\) будет оцениваться в \(\)\(62\)\(\) балла.
1 2 2 ab
5/16
2 4 3 honi hsin
19/512
3 3 10 ban ana nab
2/27