Задача C. Суперфакториальная система счисления Задача D. Мини-Тетрис 2.0
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу
размером 2×n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы
должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать.
Вам необходимо подсчитать количество способов замощения полосы 2 × n с помощью плиток
указанного вида.
Формат входных данных
Во входных данных записано одно целое число n — длина полосы (1 6 n 6 1018).
Формат выходных данных
Выведите количество способов замощения полосы с помощью плиток указанного вида. Ответ
запишите по модулю (109 + 9).
Задача C. Суперфакториальная система счисления Задача D. Мини-Тетрис 2.0
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу
размером 2×n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы
должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать.
Вам необходимо подсчитать количество способов замощения полосы 2 × n с помощью плиток
указанного вида.
Формат входных данных
Во входных данных записано одно целое число n — длина полосы (1 6 n 6 1018).
Формат выходных данных
Выведите количество способов замощения полосы с помощью плиток указанного вида. Ответ
запишите по модулю (109 + 9).
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу
размером 2×n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы
должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать.
Вам необходимо подсчитать количество способов замощения полосы 2 × n с помощью плиток
указанного вида.
Формат входных данных
Во входных данных записано одно целое число n — длина полосы (1 6 n 6 1018).
Формат выходных данных
Выведите количество способов замощения полосы с помощью плиток указанного вида. Ответ
запишите по модулю (109 + 9).
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
using namespace std;
const int MOD = 1e9 + 9;
int main() {
vector<long long> dp(n + 1);long long n;
cin >> n;
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
cout << dp[n] << endl;
return 0;
}