Линейная рекуррента


Отправить решение Решать в редакторе

Сложность: 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

Комментарии

Еще нет ни одного комментария.