Во всех заданиях необходимо вывести остаток от деления количества искомых последовательностей на число \(10^9+7\).
В некоторых задачах установлено небольшое ограничение по памяти (например, 8 MiB).
В этих задачах нужно написать решение, не хранящее все вычисленные значения функции динамического программирования.
Необходимо хранить только последний вычисленный слой и новый слой значений функции,
то есть вместо (например) двумерного массива нужно хранить два одномерных массива,
в которых будут храниться значения функции для \(n=i\) и вычисляться новые значения функции для \(n = i + 1\).
Это можно сделать используя два вектора и меняя их значения местами при помощи функции swap.
В случае превышения лимита по памяти решение может получать статус «Ошибка исполнения» на тесте.
По данному числу \(n\), \(1\le n\le 5000\), определите количество разбиений числа \(n\) на натуральные слагаемые.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n^2)\).
| Ввод | Вывод |
|---|---|
5 |
7 |
По данными числам \(n\) и \(s\), \(1\le n\le 5000\), \(1\le s \le 5000\), определите количество последовательностей из \(n\) натуральных чисел, сумма элементов которых равна \(s\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(ns)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(s)\) памяти.
| Ввод | Вывод |
|---|---|
3 5 |
6 |
Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам \(n\) и \(k\), \(1\le n\le 5000\), \(2\le k \le 5000\), определите число пилообразных последовательностей длины \(n\), составленных из чисел 1..\(k\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(nk)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(k)\) памяти.
| Ввод | Вывод |
|---|---|
3 3 |
10 |
По данным числам \(n\) и \(k\), \(1\le n\le 400\), \(1\le k\le 400\), определите количество разбиений числа \(n\) на \(k\) натуральных слагаемых.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n^2k)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(n^2)\) памяти.
| Ввод | Вывод |
|---|---|
6 3 |
3 |
По данным числам \(n\) и \(k\), \(1\le n\le 5000\), \(1\le k\le 5000\), определите количество разбиений числа \(n\) на \(k\) натуральных слагаемых.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n^2)\).
Указание. Используйте функцию \(f(n, k)\) — количество разбиений числа \(n\) на \(k\) слагаемых. При вычислении переходов рассмотрите два случая: среди слагаемых есть число 1, и такого слагаемого нет.
| Ввод | Вывод |
|---|---|
6 3 |
3 |
По данному значению \(n\), \(1\le n\le 5000\), определите количество пилообразных перестановок из \(n\) элементов.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n^2)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(n)\) памяти.
| Ввод | Вывод |
|---|---|
3 |
4 |
По данными числам \(n\) и \(k\), \(1\le n\le 10^7\), \(1\le k \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц подряд.
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n)\).
| Ввод | Вывод |
|---|---|
3 3 |
7 |
Рассмотрим последовательность из \(n\) элементов, составленную из чисел от \(1\) до \(k\). Назовём последовательность плавной, если разность двух соседних элементов не превосходит \(d\). Подсчитайте количество плавных последовательностей.
Программа получает на вход три числа: \(n\), \(k\), \(d\), \(1\le n\le 5000\), \(1\le k \le 5000\), \(0\le d \le 5000\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(nk)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(k)\) памяти.
| Ввод | Вывод |
|---|---|
5 3 1 |
99 |
По данным числам \(n\), \(k\), \(m\) определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих \(m\) единиц подряд. Ограничения: \(1\le n\le 5000\), \(0\le k\le 5000\), \(1\le m\le 5000\).
Выведите остаток от деления количества искомых последовательностей на число \(10^9+7\).
Предполагается решение сложности \(O(n^2)\).
| Ввод | Вывод |
|---|---|
5 3 2 |
1 |