โปรแกรมหาผลรวมของ 2 ยกกำลังผลรวมทุก subarray ใน Python

กำหนดลิสต์ A หา sublist ทุกตัวที่ไม่ว่าง (มี 2^n - 1 ตัว) คำนวณ sublist_sum เรียกว่า S₁, S₂, ..., S_(2^n-1) หา P = 2^S₁ + 2^S₂ + ... + 2^S_(2^n-1) ถ้า P ใหญ่ คืนค่า mod (10^9+7)

เช่น A = [2,2,3] ผลลัพธ์คือ 224

วิธีแก้ปัญหา

• ans := 1, m := 10^9+7
• สำหรับแต่ละ el ใน A
  • ans := ans * (1 + (2^el mod m))
  • ans := 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))

Input

[2,2,3]

Output

224