Problem
題目出處 PTT-Prob_Solve [問題] 面試寫到的難題 - phoenixrace
給定一個非負整數 array,找出所有不同 subarray 的數量,且每個 sub arrays 最多包含 $k$ 個奇數。
範例 1:
array = [1, 2, 3, 4] & k = 1
滿足的 sub array 有 [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4],共計 8 種
範例 2:
array = [1, 1, 2, 3] & k = 2
滿足的 sub array 有 [1], [1, 1], [1, 1, 2], [1, 2], [2], [2, 3], [3], [1, 2, 3],共計 8 種
輸入格式
多組測試資料,每組測試資料兩行,第一行兩格整數 $n$, $k$,分別為陣列個數 $N$、最多 $k$ 個奇數。接下來的一行,包含 $n$ 個非負整數為陣列內容。
- $1 \le n, k \le 10000$
- 每個陣列元素值不超過 10000
輸出格式
每組測試資料輸出一行,一個整數。
範例輸入
4 1
1 2 3 4
4 2
1 1 2 3
範例輸出
8
8