ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2122. Хэмминг

Ограничение времени: 4.0 секунды
Ограничение памяти: 256 МБ
Дана бинарная строка s длины n. Требуется для всех k от 1 до n посчитать сумму попарных расстояний Хэмминга между всеми подпоследовательностями строки s размера k. Так как ответы могут быть очень большими, выдавайте их по модулю 40 961.
Расстояние Хэмминга между двумя строками одинаковой длины – это количество позиций, в которых эти строки отличаются.

Исходные данные

Вводится строка s длины n (1 ≤ n ≤ 4 · 103), состоящая только из символов “0” и “1”.

Результат

Выведите n чисел, k-е из которых — сумма попарных расстояний Хэмминга между всеми подпоследовательностями строки s размера k по модулю 40 961.

Примеры

исходные данныерезультат
11000110111001
48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0
000
0 0 0

Замечания

Оригинальные ограничения в этой задаче были n ≤ 8 · 103, TL = 25 sec, ML = 1 GB. Ограничения были сделаны такими высокими в попытке отсечь решения со сложностью O(n3). Думаю, что теперь сдать решение с такой сложностью стало проще, а решение с правильной сложностью - сложнее. Верю, что у вас получится, но помните, что это не то, что мы задумывали :)
Автор задачи: Алексей Данилюк, Олег Меркурьев
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest