在Python中编写计算恰好具有两个项目的好餐点计数程序

假设我们有一个数组deli，其中deli [i]是第i个食品的美味程度，我们必须从此列表中找到可以制作的不同好餐点的数量。如果答案太大，则返回结果取模10 ^ 9 + 7。这里的好餐点指正是包含恰好两种不同食品项目的餐点，其美味度之和是2的n次幂。我们可以选择任何两种不同的食品制作好的餐点。

因此，如果输入为deli = [1,7,3,6,5]，则输出为3，因为我们可以制作和为2的n次幂的三对（1,3），（1,7）和（3,5）。

要解决此问题，我们将遵循以下步骤 –

$m = 10 ^ 9 + 7$
$count$：包含每个美味程度值出现频率的映射
$ans = 0$
对于count中的每个元素i，执行以下操作：
- for n in range 0 to 21，执行以下操作：
  - ， $j:=(2^n) - i$
  - 如果 $j$ 在 $计数$ 中，则
  - 如果i与j相同，则
    - $ans = ans + count[i] \cdot (count[i]-1)$
  - 否则，
    - $ans = ans + count[i] \cdot count[j]$
返回 $（ans \div 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))