Python程序：求给定数组所有子数组和的2次幂之和

假设我们有一个列表A。我们取A的所有非空子列表，我们知道一个有n个元素的列表l有(2ⁿ - 1)个非空子列表。现在，对于每个子列表，计算子列表的和（元素之和），用S₁, S₂, S₃, ... , S_(2^N-1)表示。存在一个特殊的和P，使得P = 2^S1 + 2^S2 + 2^S3 .... + 2^S(2N-1)。我们需要找到P。如果P太大，则返回P mod (10⁹ + 7)。

因此，如果输入类似于A = [2,2,3]，则输出将是子集为：

• {2} 所以 2² = 4
• {2} 所以 2² = 4
• {3} 所以 2³ = 8
• {2,2} 所以 2⁴ = 16
• {2,3} 所以 2⁵ = 32
• {2,3} 所以 2⁵ = 32
• {2,2,3} 所以 2⁷ = 128

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

为了解决这个问题，我们将遵循以下步骤：

• ans := 1
• m := 10⁹ + 7
• 对于A中的每个元素el：
  • 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))

输入

[2,2,3]

输出

224

Arnab Chakraborty

更新于：2021年10月25日

228 次浏览

启动您的职业生涯

完成课程获得认证

开始