Пълно изчерпване за 20 точки:

Първите тестовете са предвидени за всякакви експоненциални решения като например
пълно изчерпване. N е достатъчно малко, че всичко такова да работи.


Числа на Фибоначи за 30 точки:

Тук се използват само плочки I. Лесно се вижда, че винаги трябва да държим двата
реда на лентата подравнени. Това предполага да правим ДП по позицията:

dp[pos] =
  dp[pos - 1] // ако сложим едно вертикално I
  +
  dp[pos - 2] // ако сложим две хоризонтални I-та

Забележете, че dp[i] е равно на i-тото число на фибоначи.


Степени на двойката за 20 точки:

Тук се използват само плочки L. Лесно се вижда, че единственият начин да покрием
всички квадратчета е като напасваме двойки L плочки една с друга, образувайки
правоъгълници 2 на 3. След това покриваме лентата с такива провоъгълници. Има
два различни такива правоъгълника (с лявото L в нормална ориентация и с лявото L
завъртяно на 90 градуса по часовниковата стрелка). Следва че, ако N не се дели на
3, отговорът е 0, а ако N се дели на 3, отговорът е 2^(N / 3).


ДП за 20 точки:

Тук можем да използваме и двата вида плочки. За товА решение трябва да слеем
възможностите от предните две. Забележете, че следното е грешно:

dp[pos] =
  dp[pos - 1] // ако сложим едно вертикално I
  +
  dp[pos - 2] // ако сложим две хоризонтални I-та
  +
  2 * dp[pos - 3] // ако сложим две напаснати L-та

Това е, защото то изпуска покрития като първото примерно дадено в условието.

Трябва да позволим двата реда да не са подравнение. Забележете обаче, че няма нужда
разликата между покритите им дължини да надвишава 1. Нека елементите на ДП-то
ни са тройки:

{
    base,      // двата реда са равни
    top_ridge, // горният ред е с 1 по дълъг
    bot_ridge  // долният ред е с 1 по дълъг
}

Тогава имаме следната зависимост:

dp[pos].base =
  dp[pos - 1].base // ако сложим едно вертикално I
  +
  dp[pos - 2].base // ако сложим две хоризонтални I-та
  +
  dp[pos - 2].top_ridge // ако сложим едно L завъртяно на 270 градуса
  +
  dp[pos - 2].bot_ridge // ако сложим едно L завъртяно на 180 градуса

dp[pos].top_ridge =
  dp[pos - 1].base // ако сложим едно L
  +
  dp[pos - 1].bot_ridge // ако сложим едно хоризонтално I на горния ред

dp[pos].bot_ridge =
  dp[pos - 1].base // ако сложим едно L завъртяно на 90 градуса
  +
  dp[pos - 1].top_ridge // ако сложим едно хоризонтално I на долния ред

Лесно се вижда, че можем да слеем top_ridge и bot_ridge:

dp[pos].base =
  dp[pos - 1].base // ако сложим едно вертикално I
  +
  dp[pos - 2].base // ако сложим две хоризонтални I-та
  +
  2 * dp[pos - 2].ridge // ако сложим едно L завъртяно на 180 или 270 градуса

dp[pos].ridge =
  2 * dp[pos - 1].base // ако сложим едно L завъртяно на 0 или 90 градуса
  +
  dp[pos - 1].ridge // ако сложим едно хоризонтално I на един от двата реда

Това опростява кода и забързва решението, но не е нужно за вземането на точките.


Пълно ДП за 90 точки:

За 90 точки използваме горното решение, но просто имаме няколко if-а в ъпдейта на
ДП-то, така че да прибавяме компонентите, които изискват I плочки, само когато
T = 1 или T = 3, и подобно за L плочките - само когато T = 2 или T = 3.


Коментар за всички ДП решения:

По-лесно е (но не е нужно) вместо масив с цялото ДП да пазим само последните му 3
елемента: prev, curr, next. На всяка стъпка смятаме next използвайки prev и curr
и накрая правим: prev = curr; curr = next. Това би било важно, ако Memory Limit-ът
беше нисък и нямахме достатъчно памет за цялото ДП.


Решение с матрици за 100 точки:

Всички решения (освен първото) до сега са с линейна сложност по N. Това е напълно
приемливо за N <= 10^6, но е абсурдно за N <= 10^18. Тук е нужно решение с
логаритмична сложност по N.

Решението за 100 точки се базира на същата зависимост като това за 90,
но вместо да смятаме 'next' стъпка по стъпка записваме закономерността в матрица
с размери 4 на 4, повдигаме я на степен N, умножаваме началното състояние (вектор
с дължина 4) по нея и така получаваме крайното състояние. Решението е логратмично,
защото използваме бързо повдигане на степен, което ползва log N стъпки.

Това е стандартна техника за смятане на линейни рекурентни зависимости.