You are given a binary string s of length n. Compute the sum of pairwise Hamming distances between all subsequences of string s with length exactly k for all k from 1 to n. Since the answers can be very large, find them modulo 40 961.
Hamming distance between two strings of equal length is the number of positions in which these two strings are different.
The only line of input contains a string s of length n (1 ≤ n ≤ 4 · 103) containing only characters “
0” and “
Print n numbers: k-th of them must be the sum of pairwise Hamming distances between all subsequences of string s with length exactly k, taken modulo 40 961.
48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0
0 0 0
Original limitations in this problem were n ≤ 8 · 103, TL = 25 sec, ML = 1 GB. Limitations were so big to try to ban solution with complexity O(n3). I think that getting AC with that complexity is easier now, while getting AC with correct complexity is harder. I believe that you will succeed, but remember that it is not what we meant creating this problem :)
Problem Author: Alexey Danilyuk, Oleg Merkurev
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest