Loading [MathJax]/extensions/tex2jax.js

Динамическое программирование, подсчёт числа последовательностей

Во всех заданиях необходимо вывести остаток от деления количества искомых последовательностей на число \(10^9+7\).

Как создать двумерный вектор размера \(n\times m\)?

vector<vector<int>> a(n, vector<int>(m));

Как создать трёхмерный вектор размера \(n\times m\times k\)?

vector<vector<vector<int>>> a(n, vector<vector<int>>(m, vector<int>(k)));

A: Двоичные последовательности без двух единиц подряд

По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих двух единиц подряд.

Ввод	Вывод
5	13

B: Троичные последовательности без двух единиц подряд

По данному числу \(n\), \(1\le n \le 10^7\), определите количество последовательностей длины \(n\) из чисел 0, 1, 2, не содержащих двух единиц подряд.

Ввод	Вывод
2	8

С: Троичные последовательности без двух единиц и двух двоек подряд

По данному числу \(n\), \(1\le n \le 10^7\), определите количество последовательностей длины \(n\) из чисел 0, 1, 2, не содержащих двух единиц и двух двоек подряд.

Ввод	Вывод
2	7

D: Двоичные последовательности без трёх единиц подряд

По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих трёх единиц подряд.

Ввод	Вывод
5	24

E: Двоичные последовательности без трёх одинаковых элементов подряд

По данному числу \(n\), \(1\le n \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих трёх единиц и трёх нулей подряд.

Ввод	Вывод
5	16

F: Плавные числа

Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. По данному числу \(n\), \(1\le n \le 10^6\), определите количество плавных натуральных чисел, имеющих длину \(n\). Десятичная запись числа не может начинаться с нуля.

Ввод	Вывод
1	9
2	26

G: Последовательности со взаимно простыми соседями

По данными числам \(n\) и \(k\), \(1\le n\le 1000\), \(1\le k \le 100\), определите количество последовательностей длины \(n\), составленных из чисел от 1 до \(k\), в которых любые два соседних элемента взаимно простые.

Ввод	Вывод
3 5	75

H: Двоичные последовательности, не содержащие \(k\) единиц подряд

По данными числам \(n\) и \(k\), \(1\le n\le 10^5\), \(1\le k \le 100\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц подряд.

Ввод	Вывод
3 3	7

I: Двоичные последовательности, не содержащие \(k\) единиц подряд и \(k\) нулей подряд

По данными числам \(n\) и \(k\), \(1\le n\le 10^5\), \(1\le k \le 100\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц и \(k\) нулей подряд.

Ввод	Вывод
3 3	6

J: Двоичные последовательности, содержащие \(k\) единиц и не содержащих двух единиц подряд

По данными числам \(n\) и \(k\), \(1\le n\le 3\cdot10^3\), \(0\le k \le 3\cdot10^3\), определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих двух единиц подряд.

Ввод	Вывод
5 2	6

K: Пилообразные последовательности

Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам \(n\) и \(k\), \(1\le n\le 1000\), \(2\le k \le 100\), определите число пилообразных последовательностей длины \(n\), составленных из чисел 1..\(k\).

Ввод	Вывод
3 3	10

L: Последовательности длины \(n\) с суммой \(s\)

По данными числам \(n\) и \(s\), \(1\le n\le 200\), \(1\le s \le 200\), определите количество последовательностей из \(n\) натуральных чисел, сумма элементов которых равна \(s\).

Ввод	Вывод
3 5	6

M: Разбиения на слагаемые

По данному числу \(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\}\).

Указание. Заведите дополнительный параметр: \(f(n, k)\) — количество разбиений чиcла \(n\) на слагаемые, не превосходящие \(k\).

Ввод	Вывод
5	7

N: Правильные скобочные последовательности

По данному числу \(n\), \(1\le n\le 2000\), определите количество правильных скобочных последовательностей из \(n\) пар скобок.

Указание. Заведите дополнительный параметр баланс, равный разности числа открывающих и закрывающих скобок. У правильной скобочной последовательности баланс равен 0, а баланс на каждом префиксе последовательности неотрицательный. Рассмотрите функцию \(f(n, k)\) — количество последовательностей длины \(n\) баланса \(k\).

Ввод	Вывод
3	5

O: Правильные скобочные последовательности вложенности не более \(k\)

По данным числа \(n\) и \(k\), \(1\le n\le 2000\), \(1\le k\le 2000\), определите количество правильных скобочных последовательностей из \(n\) пар скобок, максимальная вложенность (максимальное значение баланса) которых не превосходит \(k\).

Ввод	Вывод
4 2	8

P: Правильные скобочные последовательности вложенности \(k\)

Ввод	Вывод
4 2	7

Q: Разбиения на \(k\) слагаемых

По данным числам \(n\) и \(k\), \(1\le n\le 50\), \(1\le k\le 50\), определите количество разбиений числа \(n\) на \(k\) натуральных слагаемых.

Ввод	Вывод
6 3	3

R: Число сочетаний

Это задание немного другого рода, и лишь отчасти имеет отношение к теме динамического программирования.

Научимся считать число сочетаний \(\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

S: Количество расстановок

Сколькими способами можно расставить в одну линию \(n\) мальчиков и \(m\) девочек так, чтобы рядом с каждым мальчиком стояла хотя бы одна девочка, и рядом с каждой девочкой стоял хотя бы один мальчик?

В этой задаче под расстановкой подразумевается последовательность из \(n+m\) элементов, среди которых \(n\) элементов «мальчик» и \(m\) элементов «девочка».

Ограничения: \(1\le n \le 2000\), \(1\le m \le 2000\).

Ввод	Вывод
2 2	4

T: Плавные последовательности

Рассмотрим последовательность из \(n\) элементов, составленную из чисел от \(1\) до \(k\). Назовём последовательность плавной, если среди любых трёх подряд идущих элементов последовательности разность между максимальным и минимальным значением в тройке не превосходит \(d\). Подсчитайте количество плавных последовательностей.

Программа получает на вход три числа: \(n\), \(k\), \(d\), \(3\le n\le 1000\), \(1\le k \le 10\), \(0\le d \le 10\).

Ввод	Вывод
5 3 1	73

U: Двоичные последовательности содержащие \(k\) единиц, не содержащие \(m\) единиц подряд

По данным числам \(n\), \(k\), \(m\) определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих \(m\) единиц подряд. Ограничения: \(1\le n\le 200\), \(0\le k\le 200\), \(1\le m\le 200\).

Ввод	Вывод
5 3 2	1

V: Пилообразные перестановки

По данному значению \(n\), \(1\le n\le 200\), определите количество пилообразных перестановок из \(n\) элементов.

Ввод	Вывод
3	4