Question

Goldman Sachs | OA | SDE -1 | 2022 | INDIA | Set-10

Answer 1

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.
Input
The only line of input contains a string s of length n (1 ≤ n ≤ 4 * 10^3) containing only characters “0” and “1”.
Output
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.

 

Input:
11000110111001

 

Output:
48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0