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

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

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

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

вход

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

рамки

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

Выход

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

Пример ввода

2
2

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

7

Пример ввода

2
4

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

71

Вопрос в том, сколько существует способов полностью покрыть прямоугольник MxN плитками 2×1 и 1×1? М и 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, чтобы проверить, какая матрица была сформирована на основе ввода. Я просто не понимаю, как строится матрица и почему суммирование элементов в последней строке должно дать результат.