Pythonでちょうど2つのアイテムでおいしい食事を数えるプログラム

deli [i]がi番目の食品の美味しさである一連のデリがあるとすると、このリストから作成できるさまざまなおいしい食事の数を見つける必要があります。答えが大きすぎる場合は、10 ^ 9 + 7を法とする結果を返します。ここで、良い食事とは、2の累乗である美味しさの合計を持つ正確に2つの異なる食品を含む食事を意味します。おいしい食事を作るために、任意の2つの異なる食品を選択できます。

したがって、入力がdeli =[1,7,3,6,5]のようである場合、ペア（1,3）、（1,7）、および（3,5）を作成できるため、出力は3になります。合計は2の累乗です。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7
• count：=各美味しさの値の頻度を含むマップ
• ans：=0
• カウントされているアイテムiごとに、
  • 0〜21の範囲のnについては、
    • j：=（2 ^ n）-i
    • jがカウントされている場合、
      • iがjと同じ場合、
        • ans：=ans + count [i] *（count [i] -1）
      • それ以外の場合、
        • ans：=ans + count [i] * count [j]
• （ans / 2）modmの商を返す

例

理解を深めるために、次の実装を見てみましょう-

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