题意回顾

给定长度为 $n$ 的序列 $a_i$，求将其划分为若干区间，使得每个区间和模 $M = 10^9+7$ 为偶数的方案数。
答案对 $M$ 取模。

数据范围：$n \leq 3\times 10^5$，$0 \leq a_i < M$。

关键观察

1. 模意义下的奇偶性

在模 $M = 10^9+7$（奇数）下，一个数 $x$ 的奇偶性就是 $x \bmod 2$，因为模运算与奇偶性兼容： $(x \bmod M) \bmod 2 = x \bmod 2$ 所以我们可以直接在前缀和模 $M$ 后考虑奇偶性。

2. 前缀和与区间和

设前缀和 $S_i = \left(\sum_{j=1}^i a_j\right) \bmod M$。
区间 $[l, r]$ 的和模 $M$ 为： $(S_r - S_{l-1}) \bmod M$ 其奇偶性 = $(S_r - S_{l-1}) \bmod 2$。

由于 $M$ 是奇数，模 $M$ 下的减法奇偶性等同于整数减法的奇偶性： $ (S_r - S_{l-1}) \bmod 2 = (S_r \bmod 2) - (S_{l-1} \bmod 2) \pmod{2} $ 即区间和偶 $\iff$ $S_r$ 与 $S_{l-1}$ 奇偶性相同。

动态规划解法

状态设计

设 $dp[i]$ 表示前 $i$ 个元素的合法划分方案数。

边界：$dp[0] = 1$（空序列算 1 种划分）。

转移方程

对于 $dp[i]$，枚举最后一段区间 $[j+1, i]$，要求 $(S_i - S_j) \bmod 2 = 0$，即 $S_i$ 与 $S_j$ 奇偶性相同。

所以： $ dp[i] = \sum_{j=0}^{i-1} [S_j \bmod 2 = S_i \bmod 2] \cdot dp[j] $

直接计算是 $O(n^2)$，不可行。

注意到我们只关心 $S_j$ 的奇偶性，设：

• $even$ = 当前所有 $S_j$ 为偶数的 $dp[j]$ 之和
• $odd$ = 当前所有 $S_j$ 为奇数的 $dp[j]$ 之和

则：

• 若 $S_i$ 偶，$dp[i] = even$
• 若 $S_i$ 奇，$dp[i] = odd$

然后更新：

• 若 $S_i$ 偶，$even = even + dp[i]$
• 若 $S_i$ 奇，$odd = odd + dp[i]$

算法步骤

1. 初始化：

   • $S = 0$（偶）
   • $dp_0 = 1$
   • $even = 1$，$odd = 0$

2. 对于 $i$ 从 $1$ 到 $n$：

   • $S = (S + a_i) \bmod M$
   • 如果 $S$ 偶：
     • $dp_i = even$
     • $even = (even + dp_i) \bmod M$
   • 如果 $S$ 奇：
     • $dp_i = odd$
     • $odd = (odd + dp_i) \bmod M$

3. 输出 $dp_n$

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$（只维护几个变量）

总结

本题的关键在于：

1. 利用模奇数的性质保持奇偶性不变
2. 将区间和条件转化为前缀和奇偶性相同
3. 用动态规划配合奇偶计数优化到 $O(n)$

最终算法简洁高效，可处理 $n \leq 3\times 10^5$ 的数据规模。