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

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

0 голосов
/ 27 ноября 2018

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

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

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

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

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

Пределы

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

Выход

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

Пример ввода 

2
2

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

7

Пример ввода 

2
4

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

71

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

...