Контест Senior Задачи на Kotlin обновлено
Число Фибоначчи по модулю для огромного n
Условие
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Для каждого запроса выведи F(n) mod (10^9 + 7).
Ввод. q (1 ≤ q ≤ 1000), затем q чисел n (0 ≤ n ≤ 10^18).
Вывод. q строк с ответами.
Как подойти
Подсказки: 2
- Нужна быстрая степень.
- Какая матрица переводит (F(n), F(n-1)) в (F(n+1), F(n))?
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.