โปรแกรมนับอาหารที่ดีด้วยสองรายการใน Python

สมมุติว่าเรามีร้านอาเรย์ที่เดลี่[i]คือความอร่อยของอาหารนั้น เราต้องหาจำนวนของอาหารดีๆ ที่เราปรุงได้จากรายการนี้ หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 10^9 + 7 ในที่นี้ มื้ออาหารที่ดี หมายถึง มื้ออาหารที่มีรายการอาหารที่แตกต่างกันสองรายการ โดยมีผลรวมของความอร่อยซึ่งเป็นกำลังสอง เราสามารถเลือกอาหาร 2 อย่างที่แตกต่างกันเพื่อทำอาหารที่ดีได้

ดังนั้น หากอินพุตเป็นเหมือนเดลี่ =[1,7,3,6,5] ผลลัพธ์จะเป็น 3 เพราะเราสามารถสร้างคู่ (1,3) (1,7) และ (3,5) ได้ ผลรวมคือยกกำลัง 2.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7
• จำนวน :=แผนที่แสดงความถี่ของค่าความอร่อยแต่ละค่า
• ตอบ :=0
• สำหรับแต่ละรายการที่ฉันนับ ทำ
  • สำหรับ n ในช่วง 0 ถึง 21 ให้ทำ
    • j:=(2^n) - ฉัน
    • ถ้า j อยู่ในการนับ แล้ว
      • ถ้าฉันเหมือนกับ j แล้ว
        • ans :=ans + count[i] *(count[i]-1)
      • มิฉะนั้น
        • ans :=ans + count[i] * count[j]
• ผลตอบแทนจากผลหารของ (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<<n)-i
         if j in count:
            if i == j:
               ans += count[i] * (count[i]-1)
            else:
               ans += count[i] * count[j]
   return (ans // 2) % m

deli = [1,7,3,6,5]
print(solve(deli))

อินพุต

[1,7,3,6,5]

ผลลัพธ์

3