Python에서 주어진 배열의 모든 하위 배열 합계의 2 거듭제곱 합계를 찾는 프로그램

<시간/>

목록 A가 있다고 가정합니다. n개의 요소가 있는 목록 l에 비어 있지 않은 하위 목록이 (2n - 1개) 있다는 것을 알고 있으므로 A의 비어 있지 않은 모든 하위 목록을 가져왔습니다. 이제 각 하위 목록에 대해 sublist_sum(요소의 합계 및 S₁ , S₂ , S₃ , ... , S_(2N-1) ). P =2^S1 인 특수 합 P가 있습니다. + 2^S2 +2^S3 .... + 2^S(2N-1) . P를 찾아야 합니다. P가 너무 크면 P mod(10^9 + 7)를 반환합니다.

따라서 입력이 A =[2,2,3]과 같으면 출력은 다음과 같습니다. 하위 집합은 다음과 같습니다.

{2} 따라서 2^2 =4
{2} 따라서 2^2 =4
{3} 따라서 2^3 =8
{2,2} 따라서 2^4 =16
{2,3} 따라서 2^5 =32
{2,3} 따라서 2^5 =32
{2,2,3} 따라서 2^7 =128

합계는 4 + 4 + 8 + 16 + 32 + 32 + 128 =224입니다.

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

ans:=1
m:=10^9+7
A의 각 el에 대해 다음을 수행합니다.
- ans :=ans *(1 + (2^el mod m))
- ans :=ans mod m
반환(m + ans-1) 모드 m

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(A):
   ans=1
   m=10**9+7

   for el in A:
      ans *= (1+pow(2,el,m))
      ans %= m
   return (m+ans-1) % m


A = [2,2,3]
print(solve(A))

입력

[2,2,3]