สมมติว่าเรามีรายการ A เราได้นำรายการย่อยที่ไม่ว่างเปล่าของ A มาทั้งหมด เนื่องจากเราทราบว่ารายการ l ที่มีองค์ประกอบ n รายการมี (2n - 1) รายการย่อยที่ไม่ว่างเปล่า ตอนนี้สำหรับรายการย่อยแต่ละรายการ เขาคำนวณ sublist_sum (ผลรวมขององค์ประกอบและแสดงด้วย S1 , S2 , S3 , ... , S(2N-1) ). มีผลรวมพิเศษ P เท่ากับว่า P =2 S1 + 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
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ:=1
- ม:=10^9+7
- สำหรับแต่ละเอลใน A ทำ
- ans :=ans *(1 + (2^el mod m))
- ans :=และ mod m
- ผลตอบแทน (m + ans-1) mod 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]
ผลลัพธ์
224
