파이썬에서 정확히 두 가지 항목으로 좋은 식사를 계산하는 프로그램

<시간/>

deli[i]가 i번째 음식의 맛인 배열 델리가 있다고 가정하면 이 목록에서 만들 수 있는 다양한 좋은 식사의 수를 찾아야 합니다. 답이 너무 크면 모듈로 10^9 + 7을 반환합니다. 여기서 좋은 식사는 정확히 2개의 다른 음식 항목을 포함하고 맛의 합이 2의 거듭제곱인 식사를 의미합니다. 우리는 좋은 식사를 위해 두 가지 다른 음식을 선택할 수 있습니다.

따라서 입력이 deli =[1,7,3,6,5]와 같으면 출력은 3이 됩니다. 왜냐하면 쌍 (1,3), (1,7) 및 (3,5) 합계는 2의 거듭제곱입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9 + 7
count :=각 맛 값의 빈도를 포함하는 지도
ans :=0
나는 각 항목에 대해 다음을 수행합니다.
- 0에서 21 사이의 n에 대해 다음을 수행합니다.
  - j:=(2^n) - 나
  - j가 카운트에 있으면
    - 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]