Триомино

Сколькими способами можно замостить прямоугольник $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

Код

#include <iostream>
#include <vector>
#define MOD 1000000
typedef long long ll;
using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {
    ll x00 = v1[0][0];
    ll x01 = v1[0][1];
    ll x10 = v1[1][0];
    ll x11 = v1[1][1];
    ll 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;
    return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
}
vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

    if (p == 1) return v;
    if ((p % 2) == 0) {
        vector<vector<ll>> vct = (pow_mod(v, p / 2));
        return multiply(vct);
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (n % 3)
        {
            cout << 0 << endl;
        }
        else
        {
            n /= 3;
            int p = 2;
            ll a1 = 1, a2 = 1;
            while (n > 0)
            {
                if (n & 1)
                {
                    vector<vector<ll>> a = { {4,-1},{1,0} };
                    a = pow_mod(a, p / 2);
                    ll tmp1 = a1;
                    ll 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;
            }
            cout << a1 % MOD << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#define MOD 1000000

typedef long long ll;

using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {

ll x00 = v1[0][0];

ll x01 = v1[0][1];

ll x10 = v1[1][0];

ll x11 = v1[1][1];

ll 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;

return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };

}

vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

if (p == 1) return v;

if ((p % 2) == 0) {

vector<vector<ll>> vct = (pow_mod(v, p / 2));

return multiply(vct);

}

int main() {

int t, n;

cin >> t;

for (int i = 0; i < t; i++)

{

cin >> n;

if (n % 3)

{

cout << 0 << endl;

}

else

{

n /= 3;

int p = 2;

ll a1 = 1, a2 = 1;

while (n > 0)

{

if (n & 1)

{

vector<vector<ll>> a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

ll tmp1 = a1;

ll 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;

}

cout << a1 % MOD << endl;

}

return 0;

}

Решение

Если 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$.