Сколько существует способов покрыть прямоугольник 8xN плитками 1x1 и 2x1?

Question

От ACM-ICPC Региональный конкурс Юго-Западной Европы 2017

Я пытаюсь понять проблему C (Macarons).

---

Пьер известен своими макаронами. Он изготавливает круглые макаруны, хранящиеся в квадратных коробках размером 1 × 1, и овальные макароны, хранящиеся в прямоугольных коробках размером 1 × 2 (или, повернутые, в прямоугольных коробках размером 2 × 1). Для буфета Пьер желает наложить прямоугольный стол размером N × M с двумя видами макарон, что означает, что стол должен быть полностью заполнен, без свободного места. Ширина N стола мала, чтобы гость мог легко захватить макароны, а длина М стола велика, чтобы вместить огромное количество гостей. Чтобы стол был красивым, ориентация макарон всегда должна быть выровнена по сторонам стола. Пьер хочет знать, сколько существует способов накрыть стол. Вы можете помочь ему?

вход

Входные данные состоят из следующих целых чисел:
• значение N, целое число, в первой строке;
• значение M, целое число, во второй строке.

рамки

Вход удовлетворяет 1 <= N <= 8 и 1

Выход

Выходные данные должны состоять из общего числа мозаичных элементов, заданных по модулю 109, в одной строке.

Пример ввода

2
2

Пример вывода

7

Пример ввода

2
4

Пример вывода

71

---

Вопрос в том, сколько существует способов полностью покрыть прямоугольник MxN плитками 2x1 и 1x1? М и N колеблются соответственно от 1 до 8 и от 1 до 10^18.

Я провел некоторое исследование и выяснил, что полезными инструментами для решения подобных проблем являются рекуррентные отношения и матричное (быстрое) возведение в степень в сочетании с использованием битовых масок.

Тем не менее, я не уверен, как реализовать решение, используя их. Есть идеи?

РЕДАКТИРОВАТЬ

Вот одно официальное решение.

#include <cstdio>
#include <vector>
#include <bits/stdc++.h>

using ::std::vector;

typedef vector<vector<long long>> mat;

const long long mod = 1000000000;

void printMat(const mat& a)
{
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < a[0].size(); j++)
        {
            std::cout << a[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

mat mul(const mat& a, const mat& b) {
    mat c = mat(a.size(), vector<long long>(b[0].size(), 0));
    for (unsigned int i = 0; i < a.size(); ++i) {
        for (unsigned int j = 0; j < b[0].size(); ++j) {
            for (unsigned int k = 0; k < b.size(); ++k) {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= mod;
            }
        }
    }
    return c;
}

mat exp(const mat& a, long long n) {
    if (n == 1ll) {
        return a;
    }
    else {
        mat b = exp(a, n / 2ll);
        mat c = mul(b, b);
        if (n % 2ll == 0) {
            return c;
        }
        else {
            return mul(c, a);
        }
    }
}

long long transitions(const mat& mem, int i, int j) {
    if (j == 0) {
        return 1;
    }
    if ((j & 1) == 0) {
        return mem[i >> 1][j >> 1];
    }
    if ((j & 3) == 1) {
        if ((i & 1) == 0) {
            return mem[i >> 2][j >> 2];
        }
        else {
            return 0;
        }
    }
    if ((i & 1) == 0) {
        return mem[i >> 2][j >> 2] + mem[i >> 1][j >> 1];
    }
    else {
        return mem[i >> 2][j >> 2];
    }
}

int main() {
    int N;
    long long M;
    scanf("%d%lld", &N, &M);
    if (N == 0 || M == 0) {
        printf("0\n");
    }
    else {
        int S = 1 << N;
        mat T = mat(S, vector<long long>(S));
        for (int i = 0; i < S; ++i) {
            for (int j = 0; j < S; ++j) {
                T[i][j] = transitions(T, i, j);
            }
        }

        printMat(T);

        mat TT = exp(T, M);

        printMat(TT);

        long long ans = 0;
        for (int i = 0; i < S; ++i) {
            ans += TT[S - 1][i];
        }
        printf("%lld\n", ans % 1000000000);
    }
    return 0;
}

Я добавил функцию printMat, чтобы проверить, какая матрица была сформирована на основе ввода. Я просто не понимаю, как строится матрица и почему суммирование элементов в последней строке должно дать результат.