Ниже в примере
.
Пусть у нас в строке длины
ровно
"сплошных" групп из 1. Например, в строке
001111011011100111111 их 4. Добавим в строку спец. символы # в начале и конце всякой такой группы:
00#1111#0#11#0#111#00#111111#
Таким образом сейчас в строке
символов. Из каждой 1-группы выбрасываем
единиц
00#11#0##0#1#00#1111#
Осталось
символов. Из 0-групп зажатых между двумя # выбрасываем один 0.
00#11####1#0#1111#
Таких нулей
. Осталось
символов.
Заменяем 0 и 1 на *, получим
**#**####*#*#****#
Я утверждаю, что по этой строке исходная восстанавливается однозначно.
Сколько таких строк? Очевидно -
.
Осталось просуммировать это дело по
.