Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự “0” hoặc “1”.
Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.
Yêu cầu: Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng k ký tự “1”.
Dữ liệu vào:
- Dòng 1: chứa một số nguyên k (0 ≤ k ≤ 106)
- Dòng 2: chứa một xâu nhị phân có độ dài ≤ 106
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là kết quả tìm được.
Input
2
01010
Output
4
Giải thích: có 4 xâu con chứa 2 ký tự 1 là: “101”, “0101”, “1010”, “01010”
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.
- Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.
- Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 5000.
Nguồn: Bài 3 HSG lớp 12 TPĐN '2018-2019