主題
題目連結：
題目意譯：
給定一整數陣列 arr。回傳有著奇數和的子陣列之數量。
由於答案可能會變得很大，所以答案應取除以 10 ^ 9 + 7 之餘數。
限制：
1 ≦ arr.length ≦ 10 ^ 5
1 ≦ arr[i] ≦ 100
範例測資：
範例 1：
輸入： arr = [1,3,5]
輸出： 4
解釋： 所有子陣列為 [[1],[1,3],[1,3,5],[3],[3,5],[5]]
所有子陣列之和為 [1,4,9,3,8,5] 。
奇數和的為 [1,9,3,5] ，所以答案為 4 。
範例 2：
輸入： arr = [2,4,6]
輸出： 0
解釋： 所有子陣列為 [[2],[2,4],[2,4,6],[4],[4,6],[6]]
所有子陣列之和為 [2,6,12,4,10,6] 。
所以子陣列都有著偶數和，所以答案為 0 。
範例 3：
輸入： arr = [1,2,3,4,5,6,7]
輸出： 16
範例 4：
輸入： arr = [100,100,99,99]
輸出： 4
範例 5：
輸入： arr = [7]
輸出： 1
解題思維：
考慮陣列 arr 的前綴和（Prefix Sums，參見這題敘述之定義）。例如 arr = [1,5,2,3,8] 的前綴和陣列 P 為
[0,1,6,8,11,19]
注意，這邊最前面包含了一個「0」，用來表示什麼數字都不取的情況下之和 = 0 。
定義前綴和陣列裡為奇數的數字個數有 X 個、偶數的有 Y 個（所以可以看到，上面開頭的「0」會屬於這裡），則所求即為
X × Y
是的，就是這麼簡單的公式。
而其原因如下：
已知「奇數減偶數」以及「偶數減奇數」的結果都是奇數，也就表示著如果我們從前綴和陣列 P 中挑出一個奇數和一個偶數相減（用大的減去小的）即可得到題目要求的一個奇數和。
而且 P 中有 X 個奇數和以及 Y 個偶數和，所以方法數為 X × Y 。
例如上面的 arr = [1,5,2,3,8] ，觀察其前綴和陣列 P：
P[0] = 0
P[1] = arr[0] = 1
P[2] = arr[0] + arr[1] = 6
P[3] = arr[0] + arr[1] + arr[2] = 8
P[4] = arr[0] + arr[1] + arr[2] + arr[3] = 11
P[5] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] = 19
我們有以下九種奇數偶數之挑法：
19 - 8 = 11
由此可以得到子陣列 arr[3] ～ arr[4]，其總和為 11 ；
19 - 6 = 13
由此可以得到子陣列 arr[2] ～ arr[4]，其總和為 13 ；
19 - 0 = 19
由此可以得到子陣列 arr[0] ～ arr[4]，其總和為 19 ；
（這也是為什麼要在 P 裡面先放一項「0」，因為每個奇數和之項次即代表著一個奇數和子陣列）
11 - 8 = 3
由此可以得到子陣列 arr[3] ～ arr[3]，其總和為 3 ；
11 - 6 = 5
由此可以得到子陣列 arr[2] ～ arr[3]，其總和為 5 ；
11 - 0 = 11
由此可以得到子陣列 arr[0] ～ arr[3]，其總和為 11 ；
8 - 1 = 7
由此可以得到子陣列 arr[1] ～ arr[2]，其總和為 7 ；
6 - 1 = 5
由此可以得到子陣列 arr[1] ～ arr[1]，其總和為 5 ；
1 - 0 = 1
由此可以得到子陣列 arr[0] ～ arr[0]，其總和為 1 ；
而以上就是所求的九種奇數和子陣列。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
