Pythonで合計が奇数になる部分配列の個数を効率的に求める方法

配列 arr が与えられます。ここで、要素の合計が奇数となる部分配列(サブ配列)の個数を求めます。答えが非常に大きくなる可能性があるため、結果は 10⁹+7 で割った余りとして返します。

例えば、入力が arr = [8,3,7] の場合、出力は 3 になります。すべての部分配列は [8]、[3]、[7]、[8,3]、[3,7]、[8,3,7] の6つであり、それぞれの合計値は 8、3、7、11、10、18 です。このうち奇数となっているのは 3、7、11 の3つであるためです。

解法のアプローチ:累積和の偶奇に着目する

すべての部分配列を素朴に列挙すると計算量が O(n²) 以上になり、大きな入力では非効率です。そこで「累積和(prefix sum)」の偶奇を利用した効率的な手法を使います。

ある部分配列 arr[i..j] の合計が奇数になるのは、「位置 j までの累積和」と「位置 i−1 までの累積和」の偶奇が異なる場合と完全に一致します。したがって、それまでに出現した累積和のうち偶数・奇数それぞれの個数を記録しておけば、各位置で O(1) で答えに加算できます。

アルゴリズムの手順

• freq を [1, 0] で初期化します(空の累積和 0 が偶数として最初から1つ存在するとみなすため)。
• ans(答え)と prefix(累積和)を 0 で初期化します。
• 配列 arr の各要素 x に対して、次の処理を繰り返します。
  • prefix に x を加算します。
  • ans に freq[1 ^ (prefix & 1)](現在と逆の偶奇を持つ累積和の個数)を加算します。
  • freq[prefix & 1] を 1 増やします。
• 最後に ans mod (10^9+7) を返します。

Pythonでの実装例

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

計算量

時間計算量は O(n)、空間計算量は O(1)(freq は固定サイズの2要素のみ)です。配列の長さ n が非常に大きい場合でも高速に動作するのが特徴です。