Chương trình đếm các bữa ăn ngon với chính xác hai món bằng Python

Giả sử chúng ta có một mảng đồ ăn ngon trong đó đồ ăn ngon [i] là độ ngon của món ăn thứ i, chúng ta phải tìm số lượng các bữa ăn ngon khác nhau mà chúng ta có thể thực hiện từ danh sách này. Nếu câu trả lời quá lớn, thì kết quả trả về modulo 10 ^ 9 + 7. Ở đây, một bữa ăn ngon có nghĩa là một bữa ăn có chính xác hai loại thực phẩm khác nhau với tổng độ ngon bằng một lũy thừa của hai. Chúng ta có thể chọn hai loại thực phẩm khác nhau để tạo nên một bữa ăn ngon.

Vì vậy, nếu đầu vào giống như Deli =[1,7,3,6,5], thì đầu ra sẽ là 3 vì chúng ta có thể tạo các cặp (1,3), (1,7) và (3,5) mà tổng là lũy thừa của 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7
• count:=một bản đồ chứa tần suất của từng giá trị độ ngon
• ans:=0
• đối với mỗi mục tôi đếm, hãy thực hiện
  • đối với n trong phạm vi từ 0 đến 21, thực hiện
    • j:=(2 ^ n) - i
    • nếu j được đếm, thì
      • nếu tôi giống với j, thì
        • ans:=ans + count [i] * (count [i] -1)
      • nếu không,
        • ans:=ans + count [i] * count [j]
• trả về thương số của (ans / 2) mod m

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[1,7,3,6,5]

Đầu ra

3