3686. 稳定子序列的数量

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP

思路

一、问题定义

给定一个整数数组 nums，定义一个子序列是 稳定的（stable），当且仅当：

不存在三个连续元素，其奇偶性完全相同。

换言之，在子序列中：

  • 连续奇数的最大长度不超过 2；
  • 连续偶数的最大长度不超过 2。

目标是计算所有 非空稳定子序列 的数量，结果对 \[ 10^9 + 7 \] 取模。

二、问题建模：从“奇偶限制”到“段长度限制”

2.1 关键观察

该约束只关心 连续同奇偶段的长度是否超过 2，而不关心更早的历史状态。

因此，在构造子序列时，只需要记录：

  • 当前子序列 最后一段的奇偶性
  • 该段的 长度是 1 还是 2

超过 2 的情况直接非法，无需建模。

2.2 状态定义

使用四个状态变量，分别表示当前所有子序列中，不同“末段形态”的数量：

  • odd1：末尾是 奇数段，且该段长度为 1
  • odd2：末尾是 奇数段，且该段长度为 2
  • even1：末尾是 偶数段，且该段长度为 1
  • even2：末尾是 偶数段，且该段长度为 2

这四种状态 覆盖了所有合法的非空稳定子序列。

三、状态转移方程

遍历数组 nums，逐个处理元素。 对每个元素，仅考虑两种行为：

  1. 不选该元素（所有已有状态保持不变）
  2. 选该元素（状态发生转移）

由于“不选”操作不会改变任何计数，转移只需描述“选该元素”的情况。

3.1 当前元素为奇数时的转移

设当前处理的元素为奇数。

（1）生成新的奇数段（长度 1）

奇数可以接在以下子序列后面，形成新的奇数段长度为 1：

  • 空子序列（生成长度为 1 的新子序列）
  • 末尾是偶数段（even1 或 even2）

因此： \[ \Delta \text{odd1} = 1 + \text{even1} + \text{even2} \]

（2）扩展已有奇数段（长度 1 → 2）

若奇数接在一个 奇数段长度为 1 的子序列后： \[ \text{odd1} \rightarrow \text{odd2} \] 对应转移为： \[ \Delta \text{odd2} = \text{odd1} \]

（3）非法转移（被禁止）

  • 奇数不能接在 odd2 后面，否则会形成长度为 3 的奇数段，违反稳定性条件。

因此，该分支直接丢弃，不产生转移。

3.2 当前元素为偶数时的转移（完全对称）

若当前元素为偶数，则奇偶角色对调：

  • 新建偶数段长度为 1：

\[ \Delta \text{even1} = 1 + \text{odd1} + \text{odd2} \]

  • 扩展偶数段长度 1 → 2：

\[ \Delta \text{even2} = \text{even1} \]

  • 禁止从 even2 再接偶数。

四、完整转移汇总（数学形式）

当处理奇数时：

\[ \begin{aligned} \text{odd1}' &= \text{odd1} + \text{even1} + \text{even2} + 1 \\ \text{odd2}' &= \text{odd2} + \text{odd1} \\ \text{even1}' &= \text{even1} \\ \text{even2}' &= \text{even2} \end{aligned} \]

当处理偶数时：

\[ \begin{aligned} \text{even1}' &= \text{even1} + \text{odd1} + \text{odd2} + 1 \\ \text{even2}' &= \text{even2} + \text{even1} \\ \text{odd1}' &= \text{odd1} \\ \text{odd2}' &= \text{odd2} \end{aligned} \]

五、初始化与最终答案

5.1 初始化

初始时尚未选择任何元素：

1
odd1 = odd2 = even1 = even2 = 0

5.2 最终答案

所有非空稳定子序列均被上述四个状态覆盖，因此答案为： \[ \text{answer} = \text{odd1} + \text{odd2} + \text{even1} + \text{even2} \] 对 \(10^9 + 7\) 取模。

六、复杂度分析

  • 时间复杂度： \[ O(n) \] 每个元素仅进行常数次状态更新。

  • 空间复杂度： \[ O(1) \] 仅使用固定数量的变量。

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    static const int mod = 1e9 + 7;

    int countStableSubsequences(vector<int>& nums) {
        // odd1  : 末尾是奇数段，长度为 1
        // odd2  : 末尾是奇数段，长度为 2
        // even1 : 末尾是偶数段，长度为 1
        // even2 : 末尾是偶数段，长度为 2
        long long odd1 = 0, odd2 = 0, even1 = 0, even2 = 0;

        for (int x : nums) {
            if (x & 1) {
                // 当前元素是奇数

                // odd2 增加：由 odd1 扩展而来（奇数段 1 → 2）
                odd2 = (odd2 + odd1) % mod;

                // odd1 增加：
                // 1. 从空序列新建 [x]
                // 2. 从 even1 接奇数
                // 3. 从 even2 接奇数
                odd1 = (odd1 + even1 + even2 + 1) % mod;
            } else {
                // 当前元素是偶数（与奇数情况完全对称）

                // even2 增加：由 even1 扩展而来（偶数段 1 → 2）
                even2 = (even2 + even1) % mod;

                // even1 增加：
                // 1. 从空序列新建 [x]
                // 2. 从 odd1 接偶数
                // 3. 从 odd2 接偶数
                even1 = (even1 + odd1 + odd2 + 1) % mod;
            }
        }

        // 所有非空稳定子序列的总数
        return (odd1 + odd2 + even1 + even2) % mod;
    }
};