|
Штрих-код
(Время: 1 сек. Память: 32 Мб Сложность: 80%)
Как известно, штрих-код состоит из чёрных полос и белых промежутков общей длиной N. Обозначим чёрные полосы единицами, а белые - нулями. Кодовое расстояние – это число позиций, в которых соответствующие символы двух штрих-кодов одинаковой длины различны.
Требуется посчитать сумму попарных кодовых расстояний между всеми подпоследовательностями штрих-кода размера K, где K перебирается от 1 до N. Для каждого K выведите ответ по модулю 998244353.
Входные данные
Входной файл INPUT.TXT содержит штрих-код из «0» и «1» длиной не более 1000.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1001 | 4 18 6 0 |
Пояснение к примеру
При K = 1:
{[11, 02], [11, 03], [11, 14], [02, 03], [02, 14], [03, 14]} = 1 + 1 + 0 + 0 + 1 + 1 = 4
При K = 2:
{[1102, 1103], [1102, 1114], [1102, 0203], [1102, 0214], [1102, 0314], [1103, 1114], [1103, 0203], [1103, 0214], [1103, 0314], [1114, 0203], [1114, 0214], [1114, 0314], [0203, 0214], [0203, 0314], [0214, 0314]} = 0 + 1 + 1 + 2 + 2 + 1 + 1 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 0 = 18
При K = 3:
{[110203, 110214], [110203, 110314], [110203, 020314], [110214, 110314], [110214, 020314], [110314, 020314]} = 1 + 1 + 2 + 0 + 1 + 1 = 6
При K = 4:
{[11020314, 11020314]} = 0
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
