Задача о подсчете строк

[oxid]

Всем привет! Помогите мне понять мое решение задачи :)

(Полное условие задачи)

Timus Online Judge писал(а):

Басня о лимоне

Ограничение времени: 1.0 секунды

Ограничение памяти: 64 МБ

Вступление
В жизни каждого программиста наступает день, когда последний контест проигран, и приходит время уходить на пенсию. Даже Три Программиста в своё время не избежали этой участи. А чтобы сохранить добрую память о себе, Программисты время от времени составляли задачи и проводили контесты. За это, конечно, не платили, но для настоящих программистов слава важнее денег.
Однако придумать хорошую задачу – только половина дела. Нужно ещё сочинить для неё политкорректный текст.
Задача
Вся проблема в том, что текст к одной из задач очередного контеста написал Третий Программист, который вообще не знает, что такое политкорректность. Он просто сочинил историю о разведении цитрусовых в домашних условиях. В результате слово «лимон» было использовано целых $N$ раз.
И это притом, что перед контестом задачу будет перечитывать известный цензор Александр К.! Которому лимоны напоминают об апельсинах, а он их терпеть не может. Сей факт очень беспокоит Первого и Второго Программистов – они прекрасно знают, что если слово «лимон» встретится Александру более $K$ раз подряд, то задача не будет допущена к контесту.
Поэтому Первый и Второй Программисты тайно сговорились в ночь накануне контеста залезть на сервер и заменить некоторые «лимоны» на гораздо более политкорректные «бананы» таким образом, чтобы задача всё-таки была допущена к контесту. Сколькими способами это можно сделать?
Исходные данные Единственная строка содержит целые числа $N$ $(1 \le N \le 10000)$ и $K$ $(0 \le K \le N)$.
Результат
Вывести искомое количество способов.
Пример
Исходные данные: $5 \quad 2$.
Результат: 24
Замечания
Обозначим слово «лимон» буквой «Л», а слово «банан» – буквой «Б». Тогда в примере исходная последовательность слов «ЛЛЛЛЛ» может быть преобразована в следующие политкорректные последовательности: «ЛЛБЛЛ», «ЛЛБЛБ», «ЛЛББЛ», «ЛЛБББ», «ЛБЛЛБ», «ЛБЛБЛ», «ЛБЛББ», «ЛББЛЛ», «ЛББЛБ», «ЛБББЛ», «ЛББББ», «БЛЛБЛ», «БЛЛББ», «БЛБЛЛ», «БЛБЛБ», «БЛББЛ», «БЛБББ», «ББЛЛБ», «ББЛБЛ», «ББЛББ», «БББЛЛ», «БББЛБ», «ББББЛ» и «БББББ».
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge

Вкратце - надо посчитать число строк состоящих из 0 и 1, при условии что строка длиной $n$ и подряд идет не более чем $k$ единиц.

Я решил двумя способами. Один из которых я понимаю, а до второго я просто догадался но хочу найти "интуицию" которая в нем скрыта.

Первый способ - заполняем массив a[i][j]
- это дины подстрок длины $j$, перед которыми находится $i$ единиц.
Получается что a[i][j] = a[i+1][i-1] + a[0][i-1]

Т.е. мы либо добавляем в конец подстроки 1, тогда увеличиваем $i$, либо ставим 0.

Это вполне интуитивное решение, которое не проходит по времени на больших числах.
Понаблюдав за происходящим я обнаружил, что на самом деле искомое число это сумма предыдущих $k+1$ чисел.

a[0][n] = a[0][n-1]+a[0][n-2]+...+a[0][n-k]

В случае когда $k = 1$, это числа Фибоначчи.

Дальше я попытался понять к каким подзадачам можно свести исходную чтобы получить $k$-боначчи.
Самое правдоподобное рассуждение выглядит так -
$a_i$ это число строк длины i закачивающихся на 0.

Их количество соответственно раскладывается на варианты -
0) Строки в которых перед 0 находится 0
1) Строки в которых перед 0 находится ровно 1 единица,
2) в которых перед 0 находится ровно 2 единицы
и т.д.

$a_i = a_{i-1}+a_{i-2}+...+a_{i-k}$

И есть аналогичная последовательность $b_i = b_{i-1}+b_{i-2}+...+b_{i-k-1} =a_{i-2}+a_{i-3}+...+a_{i-k}$ - это число строк заканчивающихся 1.
В итоге получается что число строк закачивающихся как угодно это

$a_i+b_i = a_i+a_{i-1}$

К сожалению это неверно, и правильный ответ дается самой последовательностью $a_i$.

[12d3]

Строка заканчивается либо на $0$ , либо на $01$, либо на $011$, и т.д., вплоть до нуля и $k$ единиц. Во-первых, ни один вариант не пропущен, во-вторых, такие окончания никак не влияют на то, что находится перед ним, из-за разделительного нолика. Вот тут и сидят $k$-боначчи.

[oxid]

Вот я собственно вокруг этого и верчусь ;)
У меня получается так — $a_n$ - строк длиной n оканчивающиеся на 0.
$a_{n-j}$ — число строк длиной $n$ после которых идет $j$ единиц.

Если $a_i$ это число строк длиной i, при этом $a_i=a_{i-1}+a_{i-2}+...$ — считаем разные окончания. Но мы можем после каждого этого окончания поставить либо 0 либо 1 (в последнем случае 1 добавить не можем), т.е. должно быть примерно так — $a_i= 2\cdot(a_{i-1}+a_{i-2}+...)+a_{i_k+1}$

[oxid]

12d3 в сообщении #1250449 писал(а):

С Во-первых, ни один вариант не пропущен,

А как же вариант когда строка заканчивается на 1?

[12d3]

oxid в сообщении #1250686 писал(а):

А как же вариант когда строка заканчивается на 1?

Он разбит на $k$ вариантов, в зависимости от того, сколько единиц подряд идет в конце.
Давайте я начну рассуждение, а вы продолжите.
Пусть строк длиной $n$ всего $a_n$ штук. Рассмотрим, на сколько единиц подряд может оканчиваться эта строка. Очевидно, на любое число от $0$ до $k$ включительно. Перед единицами идет нолик. Теперь зададимся вопросом, а сколько же строк длины $n$ могут оканчиваться на нолик и $m$ единиц, где $0 \le m \le k$? Столько же, сколько существует строк длины $n-m-1$. Почему? На этот вопрос предлагаю ответить вам.
А также предлагаю ответить на вопрос, почему строк длины $n$, оканчивающихся на $1$, не столько же, сколько строк длины $n-1$.
Если что, везде имеются в виду только валидные строки, в которых не более $k$ единиц подряд.