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

Arnab Chakraborty

更新于：2021年10月6日

233 次浏览

开启您的职业生涯

完成课程获得认证

开始学习