Xâu con
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”.
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:
Một số nguyên duy nhất là kết quả tìm được.
Ví dụ:
|
INPUT |
OUTPUT |
|
2 01010 |
4 |
Giải thích: có 4 xâu chứa 2 ký tự 1 là: “101”, “0101”, “1010”, “01010”
Ràng buộc:
• 40% test đầu tiên có 1 ≤ k ≤ độ dài xâu nhị phân ≤ 500
• 30% test tiếp theo có 1000 ≤ k ≤ độ dài xâu nhị phân ≤ 10000
• 30% test cuối cùng có 105 ≤ k ≤ độ dài xâu nhị phân ≤ 106