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

Расстояние Хэмминга между двумя строками одинаковой длины – это количество позиций, в которых эти строки отличаются.

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

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

Оригинальные ограничения в этой задаче были n ≤ 8 · 10³, TL = 25 sec, ML = 1 GB. Ограничения были сделаны такими высокими в попытке отсечь решения со сложностью O(n³). Думаю, что теперь сдать решение с такой сложностью стало проще, а решение с правильной сложностью - сложнее. Верю, что у вас получится, но помните, что это не то, что мы задумывали :)