20028. Counting Distinct Odd-SubArray

I'm a slow walker, but I never walk backwards.

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

Discussion