Giả sử chúng ta có một mảng arr. Chúng ta phải tìm số mảng con có tổng lẻ. Nếu câu trả lời quá lớn thì trả về mô-đun kết quả 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là arr =[8,3,7], thì đầu ra sẽ là 3 vì tất cả các mảng con là [[8], [3], [7], [8,3], [3, 7], [8,3,7]] Bây giờ tổng giá trị của chúng là [8,3,7,11,10,18] nên có ba giá trị tổng lẻ [3,7,11].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
freq:=một danh sách có hai phần tử 1 và 0
-
ans:=0
-
tiền tố:=0
-
đối với mỗi x trong arr, thực hiện
-
tiền tố:=prefix + x
-
ans:=ans + freq [1 tiền tố XOR VÀ 1]
-
freq [tiền tố VÀ 1]:=freq [tiền tố VÀ 1] + 1
-
-
return ans mod (10 ^ 9 + 7)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(arr): freq = [1, 0] ans = prefix = 0 for x in arr: prefix += x ans += freq[1 ^ prefix&1] freq[prefix &s; 1] += 1 return ans % (10**9+7) arr = [8,3,7] print(solve(arr))
Đầu vào
[8,3,7]
Đầu ra
3