นับ subarray ที่ sum เป็นคี่ ใช้ prefix sum parity: เก็บ frequency ของ prefix sum parity (0=even, 1=odd) เริ่มต้น freq[0]=1 (empty prefix) สำหรับแต่ละ x: prefix += x, ans += freq[1 ^ (prefix&1)] (ต้องการ parity ตรงข้าม), freq[prefix&1]++ ผลลัพธ์ mod 1e9+7
ขั้นตอนการทำงาน
- freq = [1, 0] # freq[even], freq[odd]
- ans = 0, prefix = 0
- วนลูป x ใน arr: prefix += x
- ans += freq[1 ^ (prefix & 1)] # จำนวน prefix ก่อนหน้าที่ parity ตรงข้าม
- freq[prefix & 1] += 1
- คืน ans % (10**9+7)
ตัวอย่างโค้ด
def solve(arr):
freq = [1, 0]
ans = prefix = 0
for x in arr:
prefix += x
ans += freq[1 ^ (prefix & 1)]
freq[prefix & 1] += 1
return ans % (10**9 + 7)
arr = [8, 3, 7]
print(solve(arr)) # Output: 3
อินพุต/เอาต์พุต
Input: [8,3,7] Output: 3
Subarrays: [8]=8(even), [3]=3(odd), [7]=7(odd), [8,3]=11(odd), [3,7]=10(even), [8,3,7]=18(even) -> 3 odd sums
