Триомино
Сколькими способами можно замостить прямоугольник $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 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
import java.util.*; import java.lang.*; import java.io.*; class Main { static long MOD=1000000; static long[][] multiply(long[][] v1) { long[][] ans=new long[2][2]; long x00 = v1[0][0]; long x01 = v1[0][1]; long x10 = v1[1][0]; long x11 = v1[1][1]; long res00, res01, res10, res11; res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD; res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD; res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD; res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD; ans[0][0]=(res00+MOD)%MOD; ans[0][1]=(res01-MOD)%MOD; ans[1][0]=(res10+MOD)%MOD; ans[1][1]=(res11-MOD)%MOD; return ans; } static long[][] pow_mod(long[][] v, int p) { if (p == 1) return v; //if ((p % 2) == 0) return multiply((pow_mod(v, p / 2))); } public static void main (String[] args) { Scanner in = new Scanner(System.in); int t=in.nextInt(); for (int i = 0; i < t; i++) { int n=in.nextInt(); if (n % 3!=0) { System.out.println(0); } else { n /= 3; int p = 2; long a1 = 1, a2 = 1; while (n > 0) { if ((n & 1)==1) { long[][] a = { {4,-1},{1,0} }; a = pow_mod(a, p / 2); long tmp1 = a1; long tmp2 = a2; a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD; a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD; } p *= 2; n >>= 1; } a1=a1%MOD; System.out.println(a1); } } } } |
Решение
Если 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