VPBINDEG - VPBINDEG
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một xâu nhị phân được gọi là bậc k nếu nó bắt đầu bằng 0, kết thúc bằng 1 và chứa một xâu con không phải tiền tố hay hậu tố có bậc k−1, đồng thời k là số nguyên lớn nhất thỏa mãn tính chất đó. Xâu rỗng được hiểu là có bậc 0.
Cho xâu nhị phân S độ dài N, xác định số xâu con bậc k của S.
Input
Dòng 1: số nguyên T là số test. Mỗi test được cho trên hai dòng:
Dòng 1: hai số nguyên N, k (2 ≤ N ≤ 10 5 ; 1 ≤ k*2 ≤ N)
Dòng 2: xâu nhị phân S độ dài N.
Tổng độ dài xâu của các test không vượt quá 10 5 .
Output
Dòng 1…T: dòng i ghi số nguyên kết quả của test i.
Example
Input:1
3 1
011
Output: 2
- Người up: only_love97
- Nguồn bài: Kì thi chọn đội tuyển quốc gia tỉnh Vĩnh Phúc nãm 2014-2015