e-olymp 236. Триомино

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

Входные данные

Первая строка содержит количество тестов $t$ ($1 \leqslant  t \leqslant  100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

Выходные данные

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

Входные данные

Выходные данные

1 3
3
4
6
3
0
11
2 4
12
15
21
9
153
571
7953
41

Код

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\
1&0 \\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\
1\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Добавить комментарий