Chương trình đếm số subarray có tổng lẻ bằng Python

Cho mảng arr. Đếm số subarray có tổng lẻ. Kết quả modulo 10^9+7.

Ví dụ: arr=[8,3,7] → subarrays: [8],[3],[7],[8,3],[3,7],[8,3,7] → tổng: 8,3,7,11,10,18 → 3 subarray tổng lẻ.

Thuật toán

• freq = [1, 0] (số prefix sum chẵn/lẻ)
• ans=0, prefix=0
• Duyệt x trong arr:
  • prefix += x
  • ans += freq[1 ^ (prefix & 1)] (số prefix trước có parity khác)
  • freq[prefix & 1] += 1
• Return ans % (10**9+7)

Code Python

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))

Input

[8,3,7]

Output

3