Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมค้นหาผลรวมของผลรวมกำลัง 2 ของผลรวม subarray ทั้งหมดของอาร์เรย์ที่กำหนดใน Python


สมมติว่าเรามีรายการ 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