Python程式：求給定陣列所有子陣列和的2次冪之和

假設我們有一個列表A。我們取A的所有非空子列表，我們知道一個有n個元素的列表l有(2n - 1)個非空子列表。現在，對於每個子列表，計算子列表的和（元素之和），用S1, S2, S3, ... , S(2N-1)表示。存在一個特殊的和P，使得P = 2S1 + 2S2 + 2S3 .... + 2S(2N-1)。我們需要找到P。如果P太大，則返回P mod (109 + 7)。

因此，如果輸入類似於A = [2,2,3]，則輸出將是子集為：

  • {2} 所以 22 = 4
  • {2} 所以 22 = 4
  • {3} 所以 23 = 8
  • {2,2} 所以 24 = 16
  • {2,3} 所以 25 = 32
  • {2,3} 所以 25 = 32
  • {2,2,3} 所以 27 = 128

總和是 4 + 8 + 16 + 32 + 128 = 188

為了解決這個問題，我們將遵循以下步驟：

  • ans := 1
  • m := 109 + 7
  • 對於A中的每個元素el：
    • ans := ans * (1 + (2el 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))

輸入

[2,2,3]

輸出

224

更新於：2021年10月25日

228 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告