使用Python找到具有奇数和的子数组的数量的程序

假设我们有一个数组arr。我们必须找到具有奇数和的子数组的数量。如果答案太大，那么返回结果取模（10^9+7）。

因此，如果输入是arr=[8,3,7]，则输出将是3，因为所有子数组都是[[8]，[3]，[7]，[8,3]，[3,7]，[8,3,7]]现在它们的总和值是[8,3,7,11,10,18]，所以有三个奇数和值[3,7,11]。

要解决这个问题，我们将按照以下步骤进行-

• freq：一个带有两个元素1和0的列表

• ans：0

• prefix：0

• 对于arr中的每个x，执行以下操作

  • prefix：= prefix + x

  • ans：= ans + freq [1 XOR prefix AND 1]

  • freq [prefix AND 1]：= freq [prefix AND 1] + 1

• 返回ansmod（10 ^ 9 +7）

让我们看一下以下实现，以获得更好的理解-

示例

def solve(arr):
    freq = [1,0]
    ans = prefix = 0
    for x in arr:
        prefix += x
        ans += freq[1 ^ prefix&1]
        freq[prefix & 1] += 1
    return ans % (10**9+7)
arr = [8,3,7]
print(solve(arr))

输入

[8,3,7]

输出

3