Giả sử chúng ta có một danh sách A. Chúng ta đã lấy tất cả các danh sách con không rỗng của A khi chúng ta biết một danh sách l có n phần tử có (2n - 1) danh sách con khác rỗng. Bây giờ đối với mỗi danh sách con, anh ta tính toán sublist_sum (tổng các phần tử và ký hiệu chúng bằng S 1 , S 2 , S 3 , ..., S (2N-1) ). Có một tổng đặc biệt P sao cho P =2 S1 + 2 S2 +2 S3 .... + 2 S (2N-1) . Chúng ta phải tìm P. Nếu P quá lớn thì trả về P mod (10 ^ 9 + 7).
Vì vậy, nếu đầu vào là A =[2,2,3], thì đầu ra sẽ là Các tập con là
- {2} nên 2 ^ 2 =4
- {2} nên 2 ^ 2 =4
- {3} nên 2 ^ 3 =8
- {2,2} nên 2 ^ 4 =16
- {2,3} nên 2 ^ 5 =32
- {2,3} nên 2 ^ 5 =32
- {2,2,3} nên 2 ^ 7 =128
Tổng là 4 + 4 + 8 + 16 + 32 + 32 + 128 =224
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=1
- m:=10 ^ 9 + 7
- đối với mỗi el trong A, thực hiện
- ans:=ans * (1 + (2 ^ el mod m))
- ans:=ans mod m
- return (m + ans-1) mod m
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
[2,2,3]
Đầu ra
224