--->
3 задач
<---
Источники
Известны первые \(k\) членов последовательности – \(a_1, a_2, \dots, a_k\) (\(0 \leq a_i \leq 9\), где \(i = 1, 2, \dots, k\)). Другие члены последовательности вычисляются по следующему правилу: \(a_i = \sum_{j=i-k}^{i-1}a_j\), то есть каждый следующий член равен сумме \(k\) предыдущих. Необходимо найти последние \(r\) цифр числа \(a_n\).
В первой строке входного файла находятся \(3\) целых числа – \(k\), \(n\) и \(r\) (\(1 \leq k \leq 20\), \(1 \leq n \leq 10^{18}\), \(1 \leq r \leq 9\)). В следующей строке находится \(k\) чисел – \(a_1, a_2, \dots, a_k\).
Первой строкой выходного файла выведите \(r\) цифр числа \(a_n\). Ведущие нули следует опустить.
1. Тесты, в которых \(r = 1\), будут оцениваться 75 баллами:
1.1 Тесты, в которых \(n<10^6\), будут оцениваться 25 баллами.
1.2 Тесты, в которых \(n \geq 10^6\), будут оцениваться 50 баллами:
1.2.1 Тесты, в которых \(k < 7\), будут оцениваться 30 баллами.
1.2.2 Тесты, в которых \(6 < k < 11\), будут оцениваться 20 баллами.
2. Тесты, в которых \(r > 1\), будут оцениваться 25 баллами.
2 5 1 1 2
8
1 100001 1 5
5
На вход программе подаются 3 целых неотрицательных числа x, N и P, не превосходящих 2 * 109. Кроме того P > 0. Требуется вычислить значение x в степени N по модулю P.
2 10 1000
24
Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(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