สมมติว่าเรามีอาร์เรย์ deli โดย deli[i] คือความอร่อยของอาหารชิ้นที่ i เราต้องหาจำนวนมื้ออาหารที่ดีที่แตกต่างกันที่เราสามารถทำจากรายการนี้ ถ้าคำตอบใหญ่เกินไป ให้ return ผลลัพธ์ modulo 10^9 + 7 ในที่นี้ มื้ออาหารที่ดี หมายถึงมื้ออาหารที่มีอาหารสองชนิดที่ต่างกันพอดี ซึ่งผลรวมของความอร่อยเป็นกำลังของสอง เราสามารถเลือกอาหารสองชนิดที่ต่างกันใดๆ เพื่อทำมื้ออาหารที่ดี
เช่น ถ้าอินพุตคือ deli = [1,7,3,6,5] ผลลัพธ์จะเป็น 3 เพราะเราสามารถจับคู่ (1,3), (1,7) และ (3,5) ซึ่งผลรวมเป็นกำลังของ 2
วิธีแก้ปัญหา
- m := 10^9 + 7
- count := แมปที่มีความถี่ของแต่ละค่าความอร่อย
- ans := 0
- สำหรับแต่ละ item i ใน count:
- สำหรับ n ในช่วง 0 ถึง 21:
- j := (2^n) - i
- ถ้า j อยู่ใน count:
- ถ้า i เท่ากับ j: ans := ans + count[i] * (count[i]-1)
- มิฉะนั้น: ans := ans + count[i] * count[j]
- สำหรับ n ในช่วง 0 ถึง 21:
- return ผลหารของ (ans/2) mod m
ตัวอย่าง
from collections import Counter
def solve(deli):
m = 10**9 + 7
count = Counter(deli)
ans = 0
for i in count:
for n in range(22):
j = (1<
อินพุต
[1,7,3,6,5]
เอาต์พุต
3
