Chương trình đếm bữa ăn ngon với đúng hai món trong Python

Giả sử ta có mảng deli trong đó deli[i] là độ ngon của món thứ i. Cần tìm số bữa ăn ngon khác nhau có thể làm. Kết quả modulo 10^9 + 7. Bữa ăn ngon là bữa có đúng 2 món khác nhau mà tổng độ ngon là lũy thừa của 2.

Ví dụ: deli = [1,7,3,6,5], đầu ra = 3 vì có các cặp (1,3), (1,7), (3,5) có tổng là lũy thừa của 2.

Giải pháp

Đếm tần suất mỗi độ ngon, sau đó kiểm tra các cặp có tổng là lũy thừa của 2:

• m := 10^9 + 7
• count := map tần suất các giá trị deli
• ans := 0
• Với mỗi i trong count:
  • Với n từ 0 đến 21:
    • j := (2^n) - i
    • Nếu j trong count:
      • Nếu i == j: ans += count[i] * (count[i]-1)
      • Ngược lại: ans += count[i] * count[j]
• Trả về (ans // 2) % m

Ví dụ minh họa

Xem 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