Tiền tố vô hạn

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.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 xâu nhị phân $s$ độ dài $n$ chỉ gồm các ký tự 0 và 1. Xây dựng xâu vô hạn $t$ bằng cách nối liên tiếp vô số bản sao của $s$ , tức là $t = s s s s \dots$ . Ví dụ với $s = 10010$ thì $t = 100101001010010 \dots$

Định nghĩa cân bằng của một xâu $q$ là ${cnt}_{0, q} - {cnt}_{1, q}$ , trong đó ${cnt}_{0, q}$ và ${cnt}_{1, q}$ lần lượt là số lần xuất hiện của 0 và 1 trong $q$ .

Hãy đếm số tiền tố (kể cả tiền tố rỗng) của $t$ có cân bằng đúng bằng $x$ . Nếu số tiền tố thoả mãn là vô hạn thì in ra -1.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ — số test ( $1 \leq T \leq 100$ ).
Với mỗi test:
- Dòng đầu chứa hai số nguyên $n$ và $x$ ( $1 \leq n \leq 10^{5}$ , $- 10^{9} \leq x \leq 10^{9}$ ).
- Dòng thứ hai chứa xâu nhị phân $s$ độ dài $n$ .

Tổng $n$ trên tất cả các test không vượt quá $10^{5}$ .

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là đáp án cho một test: số tiền tố có cân bằng bằng $x$ , hoặc -1 nếu vô hạn.

Ví dụ

Input	Output	Giải thích
4 6 10 010010 5 3 10101 1 0 0 2 0 01	3 0 1 -1	Test 1: ba tiền tố có cân bằng $10$ có độ dài $28, 30, 32$ . Test 4: $s = 01$ có cân bằng tổng bằng $0$ nên cứ sau mỗi chu kỳ cân bằng lại quay về $0$ — vô hạn tiền tố thoả mãn.
1 5 -3 11111	1	$s$ toàn `1` nên cân bằng giảm dần $0, - 1, - 2, - 3, \dots$ Chỉ duy nhất tiền tố độ dài $3$ có cân bằng $- 3$ .

Bình luận

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