Số xâu con tốt

Điểm: 5,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một xâu nhị phân $s$ (mỗi ký tự là 0 hoặc 1).

Gọi $f (t)$ là giá trị thập phân của số được biểu diễn ở hệ nhị phân bởi xâu $t$ (cho phép có các chữ số 0 đứng đầu). Ví dụ: $f (011) = 3$ , $f (00101) = 5$ , $f (10) = 2$ , $f (000) = 0$ , $f (000100) = 4$ .

Một xâu con liên tiếp $s_{l} s_{l + 1} \dots s_{r}$ được gọi là tốt nếu

$r - l + 1 = f (s_{l} s_{l + 1} \dots s_{r}) .$

Tức là độ dài của xâu con đúng bằng giá trị thập phân của nó khi đọc như số nhị phân (cho phép có các chữ số 0 đứng đầu).

Cho $t$ truy vấn độc lập, với mỗi xâu $s$ hãy đếm số xâu con tốt của $s$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số truy vấn.
Mỗi dòng tiếp theo chứa một xâu $s$ chỉ gồm các ký tự 0 và 1.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa số xâu con tốt của $s$ .

Ràng buộc

$1 \leq t \leq 1000$
$1 \leq | s | \leq 2 \cdot 10^{5}$
$\sum | s | \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
4 0110 0101 00001000 0001000	4 3 4 3	Với $s = 0110$ , bốn xâu con tốt là: $s_{2} = 1$ (độ dài 1, giá trị 1), $s_{3} = 1$ , $s_{3} s_{4} = 10$ (độ dài 2, giá trị 2), và $s_{1} s_{2} s_{3} = 011$ (độ dài 3, giá trị 3).
1 0101	3	Với $s = 0101$ : ba xâu con tốt là $s_{2} = 1$ , $s_{4} = 1$ , và $s_{2} s_{3} = 10$ (độ dài 2, giá trị 2).

Bình luận

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