Задача №3374. Последовательность
Известны первые \(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