Vị Trí Bit Một

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một xâu nhị phân độ dài $n$ (chỉ gồm ký tự '0' và '1'). Với mỗi khoảng cách $k$ từ $1$ đến $n - 1$ , hãy đếm số cách chọn hai vị trí $i$ và $j$ sao cho $i - j = k$ và cả hai vị trí đều có bit '1'.

Dữ liệu vào

Một dòng duy nhất chứa xâu nhị phân độ dài $n$ .

Dữ liệu ra

$n - 1$ số nguyên — với mỗi $k$ từ $1$ đến $n - 1$ , số cặp $(i, j)$ thỏa mãn $i - j = k$ và $s_{i} = s_{j} =$ '1'.

Ràng buộc

$2 \leq n \leq 2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
1001011010	1 2 3 0 2 1 0 1 0	Với $k = 1$ : cặp $(5, 4)$ → 1. Với $k = 2$ : cặp $(3, 1), (7, 5)$ → 2.
11	1	Cả hai vị trí đều là '1', khoảng cách $k = 1$ → 1 cặp.

Bình luận

Không có bình luận tại thời điểm này.