难度: Medium
给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
示例 1：
输入：arr = [1,3,5] 输出：4 解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。 所有子数组的和为 [1,4,9,3,8,5]. 奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：
输入：arr = [2,4,6] 输出：0 解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。 所有子数组和为 [2,6,12,4,10,6] 。 所有子数组和都是偶数，所以答案为 0 。
示例 3：
输入：arr = [1,2,3,4,5,6,7] 输出：16
示例 4：
输入：arr = [100,100,99,99] 输出：4
示例 5：
输入：arr = [7] 输出：1
提示：
1 <= arr.length <= 10^51 <= arr[i] <= 100运行时间: 86 ms
内存: 20.5 MB
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
odd = 0
even = 1 # 初始0表示什么都不选的情况
j = 0
for i in arr:
j+=i
if j&1:
odd+=1
else:
even+=1
# 一个奇数前缀配一个偶数前缀组成一个满足要求的区间，乘法原理
return (odd*even)%1000000007
这个题解利用了数组的前缀和来确定子数组的和是否为奇数。通过维护两个计数器：odd（记录以当前元素结尾的数组的前缀和为奇数的情况数）和even（记录为偶数的情况数，初始为1代表空子数组的前缀和为0，是偶数）。遍历数组，更新当前的前缀和。如果前缀和为奇数，则增加odd计数；如果为偶数，则增加even计数。最终，奇数前缀和的数量乘以偶数前缀和的数量就是结果，因为每个奇数前缀和都可以与之前的任意一个偶数前缀和组合形成一个和为奇数的子数组。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
odd = 0 # 奇数前缀和的计数
even = 1 # 偶数前缀和的计数，包括初始的和为0的情况
j = 0 # 前缀和
for i in arr:
j += i # 更新前缀和
if j & 1: # 如果前缀和是奇数
odd += 1 # 增加奇数计数
else: # 如果前缀和是偶数
even += 1 # 增加偶数计数
# 结果是奇数前缀和与偶数前缀和的组合数，模 10^9 + 7
return (odd * even) % 1000000007
在算法中初始化偶数前缀和计数器为1是因为考虑了一个初始的空数组情况，其前缀和为0，而0是一个偶数。这样的初始化有助于处理数组中第一个元素就是奇数的情况，确保能正确统计从数组开始到当前位置的子数组的和。如果不将其初始化为1，那么在数组第一个元素为奇数时，将无法计入以它为结束点的子数组。
当当前的前缀和是奇数时，累加odd计数器的原因在于记录下有多少个以当前元素结尾的前缀和是奇数。这是因为任何从数组开始到当前元素的子段（前缀）如果其和是奇数，那么这个前缀本身就可以被视为一个和为奇数的子数组。此外，这些奇数前缀和在后续的计算中，当再次遇到奇数前缀和时，可以与之前记录的偶数前缀和组合，形成新的和为奇数的子数组。
这种组合形成子数组和为奇数的原理基于数学性质：两个奇数相加得到偶数，两个偶数相加得到偶数，但一个奇数和一个偶数相加得到奇数。在解题方法中，通过计算所有奇数前缀和与偶数前缀和之间的组合，可以找到所有可能的子数组，这些子数组的和为奇数。这是因为每个奇数前缀和都可以与之前的任意一个偶数前缀和相减（即两个前缀和之间的元素组成的子数组），结果是奇数。
在许多编程竞赛和算法实现中，需要对结果取模以防止数字溢出并保持结果的大小在可管理的范围内。10^9 + 7是一个常用的大质数，使用它作为模数有几个好处：它足够大，可以避免常见计算中的溢出；同时作为质数，它在数学运算中，尤其是在需要使用逆元时，具有良好的数学性质。使用质数作为模数可以避免一些在模运算中可能出现的问题。