По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих двух единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 |
13 |
По данному числу \(n\), \(1\le n \le 10^7\), определите количество последовательностей длины \(n\) из чисел 0, 1, 2, не содержащих двух единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
2 |
8 |
По данному числу \(n\), \(1\le n \le 10^7\), определите количество последовательностей длины \(n\) из чисел 0, 1, 2, не содержащих двух единиц и двух двоек подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
2 |
7 |
По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих трёх единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 |
24 |
По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих трёх единиц и трёх нулей подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 |
16 |
Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. По данному числу \(n\), \(1\le n \le 10^6\), определите количество плавных натуральных чисел, имеющих длину \(n\). Десятичная запись числа не может начинаться с нуля.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
1 |
9 |
2 |
26 |
По данными числам \(n\) и \(k\), \(1\le n\le 1000\), \(1\le k \le 100\), определите количество последовательностей длины \(n\), составленных из чисел от 1 до \(k\), в которых любые два соседних элемента взаимно простые.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 5 |
75 |
По данными числам \(n\) и \(k\), \(1\le n\le 10^5\), \(1\le k \le 100\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 3 |
7 |
По данными числам \(n\) и \(k\), \(1\le n\le 10^5\), \(1\le k \le 100\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц и \(k\) нулей подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 3 |
6 |
По данными числам \(n\) и \(k\), \(1\le n\le 3\cdot10^3\), \(0\le k \le 3\cdot10^3\), определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих двух единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 2 |
6 |
Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам \(n\) и \(k\), \(1\le n\le 1000\), \(2\le k \le 100\), определите число пилообразных последовательностей длины \(n\), составленных из чисел 1..\(k\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 3 |
10 |
По данными числам \(n\) и \(s\), \(1\le n\le 200\), \(1\le s \le 200\), определите количество последовательностей из \(n\) натуральных чисел, сумма элементов которых равна \(s\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 5 |
6 |
По данному числу \(n\), \(1\le n\le 200\), определите количество разбиений числа \(n\) на натуральные слагаемые. Разбиения, отличающиеся перестановкой слагаемых, считаются совпадающими. Например, для числа \(5\) есть такие разбиения: \(\{5\}, \{4, 1\}, \{3, 2\}, \{3, 1, 1\}, \{2, 2, 1\}, \{2, 1, 1, 1\}, \{1, 1, 1, 1, 1\}\).
Выведите остаток от деления количества разбиений на число \(10^9+7\).
Указание. Заведите дополнительный параметр: \(f(n, k)\) — количество разбиений чиcла \(n\) на слагаемые, не превосходящие \(k\).
| Ввод | Вывод |
|---|---|
5 |
7 |
По данному числу \(n\), \(1\le n\le 2000\), определите количество правильных скобочных последовательностей из \(n\) пар скобок.
Указание. Заведите дополнительный параметр баланс, равный разности числа открывающих и закрывающих скобок. У правильной скобочной последовательности баланс равен 0, а баланс на каждом префиксе последовательности неотрицательный. Рассмотрите функцию \(f(n, k)\) — количество последовательностей длины \(n\) баланса \(k\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 |
5 |
По данным числа \(n\) и \(k\), \(1\le n\le 2000\), \(1\le k\le 2000\), определите количество правильных скобочных последовательностей из \(n\) пар скобок, максимальная вложенность (максимальное значение баланса) которых не превосходит \(k\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
4 2 |
8 |
По данным числа \(n\) и \(k\), \(1\le n\le 2000\), \(1\le k\le 2000\), определите количество правильных скобочных последовательностей из \(n\) пар скобок, максимальная вложенность (максимальное значение баланса) которых равна в точности \(k\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
4 2 |
7 |
По данным числам \(n\) и \(k\), \(1\le n\le 50\), \(1\le k\le 50\), определите количество разбиений числа \(n\) на \(k\) натуральных слагаемых.
Выведите остаток от деления количества искомых разбиений на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
6 3 |
3 |
Это задание немного другого рода, и лишь отчасти имеет отношение к теме динамического программирования.
Научимся считать число сочетаний \(\text{C}_n^k\) быстро. Воспользуемся соотношением
\[ \text{C}_n^k = \dfrac{n!}{k!(n-k)!}=\dfrac{n\cdot(n-1)!}{k\cdot (k-1)!(n-k)!}=\frac{n}{k}\text{C}_{n-1}^{k-1}. \]Вам даны числа \(n\) и \(k\), \(0\le k\le n\le 10^6\). Найдите остаток от деления значения \(\text{C}_{n}^{k}\) на \(10^9+7\).
| Ввод | Вывод |
|---|---|
6 3 |
20 |
Сколькими способами можно расставить в одну линию \(n\) мальчиков и \(m\) девочек так, чтобы рядом с каждым мальчиком стояла хотя бы одна девочка, и рядом с каждой девочкой стоял хотя бы один мальчик?
В этой задаче под расстановкой подразумевается последовательность из \(n+m\) элементов, среди которых \(n\) элементов «мальчик» и \(m\) элементов «девочка».
Ограничения: \(1\le n \le 2000\), \(1\le m \le 2000\).
Выведите остаток от деления количества искомых расстановок на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
2 2 |
4 |
Рассмотрим последовательность из \(n\) элементов, составленную из чисел от \(1\) до \(k\). Назовём последовательность плавной, если среди любых трёх подряд идущих элементов последовательности разность между максимальным и минимальным значением в тройке не превосходит \(d\). Подсчитайте количество плавных последовательностей.
Программа получает на вход три числа: \(n\), \(k\), \(d\), \(3\le n\le 1000\), \(1\le k \le 10\), \(0\le d \le 10\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 3 1 |
73 |
По данным числам \(n\), \(k\), \(m\) определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих \(m\) единиц подряд. Ограничения: \(1\le n\le 200\), \(0\le k\le 200\), \(1\le m\le 200\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
5 3 2 |
1 |
По данному значению \(n\), \(1\le n\le 200\), определите количество пилообразных перестановок из \(n\) элементов.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
| Ввод | Вывод |
|---|---|
3 |
4 |