시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
25 초 | 1024 MB | 2 | 0 | 0 | 0.000% |
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 \le n \le 8 \cdot 10^{3}$) containing only characters "0
" and "1
".
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$.
11000110111001
48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0
000
0 0 0