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: SUBSTR.INP
Dữ liệu ra: SUBSTR.OUT
|
SUBSTR.INP |
SUBSTR.OUT |
|
2 01010 |
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: gọi n là độ dài xâu
- 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 ≤ 1.000.000.