Линейная рекуррента
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Линейная рекуррента
Последовательность задана так: a_0, …, a_{d-1} известны, а для i ≥ d выполняется a_i = c_1·a_{i-1} + c_2·a_{i-2} + … + c_d·a_{i-d}. Найдите a_N по модулю 10^9 + 7.
Ввод. d (1 ≤ d ≤ 10) и N (0 ≤ N ≤ 10^18); затем d чисел a_0 … a_{d-1}; затем d чисел c_1 … c_d (все от 0 до 10^9+6).
Вывод. Одно число.
Пример 1
Ввод:
2 10
0 1
1 1
Вывод:
55
Комментарии