สมมติว่าเรามีอาร์เรย์ arr เราต้องหาจำนวนอาร์เรย์ย่อยที่มีผลรวมคี่ หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 10^9+7
ดังนั้น ถ้าอินพุตเป็นเหมือน arr =[8,3,7] ผลลัพธ์จะเป็น 3 เพราะอาร์เรย์ย่อยทั้งหมดเป็น [[8],[3],[7],[8,3],[3, 7],[8,3,7]] ตอนนี้ค่าผลรวมของมันคือ [8,3,7,11,10,18] ดังนั้นจึงมีค่าผลรวมคี่สามค่า [3,7,11]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
freq :=รายการที่มีสององค์ประกอบ 1 และ 0
-
ตอบ :=0
-
คำนำหน้า :=0
-
สำหรับแต่ละ x ใน arr ทำ
-
คำนำหน้า :=คำนำหน้า + x
-
ans :=ans + freq[1 XOR prefix AND 1]
-
freq[prefix AND 1] :=freq[prefix AND 1] + 1
-
-
ส่งคืน mod (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 &s; 1] += 1 return ans % (10**9+7) arr = [8,3,7] print(solve(arr))
อินพุต
[8,3,7]
ผลลัพธ์
3
