Задача №115211. Красивые последовательности
Дано множество \(A\), элементами которого являются различные целые числа от \(1\) до \(8\).
Рассмотрим последовательность \([a_1, a_2, \ldots, a_n]\) из \(n\) целых чисел, каждое из которых выбрано из множества \(A\). Будем называть эту последовательность красивой , если для любого числа \(x\) все элементы последовательности, равные \(x\), находятся на расстоянии не меньше \(x\) друг от друга. Иначе говоря, для любого числа \(x\) и для любых двух индексов \(1 \le i < j \le n\), таких, что \(a_i = a_j = x\), должно выполняться неравенство \(j - i \ge x\).
Требуется посчитать количество красивых последовательностей для заданного числа \(n\) и множества \(A\), и вывести остаток от деления этого количества на число \(10^9+7\).
В первой строке ввода даны два целых числа \(n\) и \(m\) — длина последовательности и количество элементов множества \(A\) (\(1 \le n \le 100\), \(1 \le m \le 8\)).
Во второй строке ввода даны \(m\) различных целых чисел \(a_i\) в порядке возрастания — элементы множества \(A\) (\(1 \le a_i \le 8\), \(a_i < a_{i + 1}\)).
Выведите одно целое число — остаток от деления количества красивых последовательностей на число \(10^9 + 7\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 5 | \(A = \{1, 2\}\), \(n \le 10\) | первая ошибка | |
| 2 | 10 | \(A = \{1, 2\}\), \(n \le 30\) | 1 | первая ошибка |
| 3 | 15 | \(A = \{1, 2\}\) | 1, 2 | первая ошибка |
| 4 | 20 | \(A = \{1, k\}\) для \(2 \le k \le 8\) | 1, 2, 3 | первая ошибка |
| 5 | 30 | \(a_i \le 5\) | 1, 2, 3 | первая ошибка |
| 6 | 20 | нет | 1, 2, 3, 4, 5 | первая ошибка |
В примере красивыми являются последовательности \([1, 1, 1]\), \([1, 1, 2]\), \([1, 2, 1]\), \([2, 1, 1]\), \([2, 1, 2]\).
Последовательности \([2, 2, 2]\), \([1, 2, 2]\), \([2, 2, 1]\) красивыми не являются, так как в каждой из них существуют два элемента со значением \(2\), находящиеся на расстоянии \(1\) друг от друга.
3 2 1 2
5