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的商

示例

让我们看看下面的实现以更好地理解:

Open Compiler
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]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

3

更新于:2021年10月6日

233 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告