20028. Counting Distinct Odd-SubArray

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