Câu 5. Đoạn K số đối xứng (4,0 điểm; Đề TS vào 10 – Lào Cai 2026 – 2027)

Số đối xứng là số nguyên dương khi viết ngược lại thì vẫn bằng chính nó. Ví dụ: Các số 111, 121, 2, 3, 22322 là các số đối xứng; Các số 123, 113 không phải là số đối xứng. Cho dãy gồm N số nguyên dương A₁, A₂,…, A_N và số nguyên K.
Yêu cầu: Hãy đếm số đoạn con liên tiếp có chỉ số từ L đến R (1 ≤ L ≤ R ≤ N ) của dãy số trên sao cho đoạn đó chứa đúng K số đối xứng.

• Dòng đầu chứa hai số nguyên N, K (0 ≤ K ≤ N ≤ 10⁶).
• Dòng thứ hai chứa N số nguyên dương A₁, A₂,…, A_N (A_i ≤ 10⁹; 1 ≤ i ≤ N).

Kết quả: In ra số lượng đoạn con liên tiếp có đúng K số đối xứng.

Ví dụ:

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài với 1 ≤ N ≤ 5.10³.
• Có 30% số test tương ứng với 30% số điểm của bài với 1 ≤ N ≤ 10⁵.
• Có 40% số test còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.