CSES - One Bit Positions | Các vị trí bit 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu nhị phân có độ dài \(n\). Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\) đếm số cách chọn \(i\) và \(j\) sao cho \(i - j = k\) và cả hai vị trí đều chứa bit \(1\).

Input

  • Một dòng duy nhất chứa một xâu chỉ bao gồm kí tự \(0\) và \(1\).

Output

  • Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\), in ra số cách có thể chọn được hai vị trí như vậy.

Constraints

  • \(2 \ \leq \ n \ \leq \ 2 \times 10^5\)

Example

Sample input

1001011010

Sample output

1 2 3 0 2 1 0 1 0

Bình luận