HSG lớp 9 TP Đà Nẵng 2024 - Bài 3 - Chùm đèn

Đề bài

Dọc theo khu vườn nhà Tí có \(n\) chùm bóng đèn được đánh số từ \(1\) đến \(n\). Chùm bóng đèn thứ \(i\) có \(a_i\) bóng.

Để chuẩn bị cho buổi tiệc sinh nhật, Tí muốn chọn một dãy liên tiếp gồm một hoặc nhiều chùm đèn để trang trí khu vực chụp hình. Dãy được chọn phải có đúng \(k\) chùm đèn mà số lượng bóng trong chùm là số lẻ.

Hãy tính số cách chọn dãy chùm đèn thỏa mãn yêu cầu của Tí.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\), lần lượt là số chùm đèn và số chùm đèn có số bóng lẻ cần xuất hiện trong dãy được chọn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số bóng của chùm đèn thứ \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất là số cách chọn một dãy chùm đèn liên tiếp có đúng \(k\) chùm chứa số bóng lẻ.

Ràng buộc

• \(1 \le k \le n \le 10^6\).
• \(1 \le a_i \le 10^6\).

Subtask

• Subtask 1 (30%): \(1 \le n \le 100\).
• Subtask 2 (30%): \(100 < n \le 5000\).
• Subtask 3 (40%): Không có ràng buộc thêm.

4 2
1 3 2 3

3

Giải thích

Với dãy \([1,3,2,3]\), có ba dãy liên tiếp chứa đúng hai chùm đèn có số bóng lẻ:

• Các chùm đèn từ vị trí \(1\) đến vị trí \(2\): \([1,3]\).
• Các chùm đèn từ vị trí \(1\) đến vị trí \(3\): \([1,3,2]\).
• Các chùm đèn từ vị trí \(2\) đến vị trí \(4\): \([3,2,3]\).

Vì vậy, kết quả cần in ra là \(3\).