Python程式：計算恰好包含兩項的優質餐食數量

假設我們有一個數組deli，其中deli[i]是第i種食物的美味程度，我們需要找到可以從這個列表中製作的不同優質餐食的數量。如果答案過大，則返回結果模10^9 + 7。這裡，優質餐食是指恰好包含兩種不同食物，且美味程度之和為2的冪的餐食。我們可以選擇任意兩種不同的食物來製作優質餐食。

因此，如果輸入類似於deli = [1,7,3,6,5]，則輸出將為3，因為我們可以製作對(1,3)，(1,7)和(3,5)，它們的和是2的冪。

為了解決這個問題，我們將遵循以下步驟：

  • m := 10^9 + 7
  • count := 一個包含每個美味程度值頻率的對映
  • ans := 0
  • 對於count中的每個專案i，執行：
    • 對於n從0到21，執行：
      • j:= (2^n) - i
      • 如果j在count中，則：
        • 如果i等於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

更新於：2021年10月6日

233 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告