DeepSeek LeetCode 3686. 稳定子序列的数量 C++实现

这道题的难点在于，当我们逐个处理元素时，只要知道当前稳定子序列最后两个元素的奇偶性，就能判断能否追加新的元素。因此可以用状态机 DP，只需维护 4 个状态。

```cpp
class Solution {
public:
int countStableSubsequences(vector<int>& nums) {
const int MOD = 1e9 + 7;
// 状态定义：
// f[0][0]: 以偶数结尾，且末尾连续偶数长度为1
// f[0][1]: 以偶数结尾，且末尾连续偶数长度为2
// f[1][0]: 以奇数结尾，且末尾连续奇数长度为1
// f[1][1]: 以奇数结尾，且末尾连续奇数长度为2
long long f[2][2] = {};

for (int x : nums) {
int p = x & 1; // 当前元素奇偶性，0偶1奇
int q = p ^ 1; // 相反奇偶性

// 追加到末尾为 q 的子序列后面（奇偶性不同，新连续段长度为1）
long long addToDiff = (f[q][0] + f[q][1]) % MOD;
// 当前元素单独成为一个子序列
long long alone = 1;
// 新的“末尾连续长度为1”的状态
long long newLen1 = (f[p][0] + addToDiff + alone) % MOD;
// 新的“末尾连续长度为2”的状态（只能追加到末尾连续长度为1的同奇偶性子序列后）
long long newLen2 = (f[p][1] + f[p][0]) % MOD;

// 更新状态
f[p][0] = newLen1;
f[p][1] = newLen2;
}

return (f[0][0] + f[0][1] + f[1][0] + f[1][1]) % MOD;
}
};
```

⚙️ 核心思路：状态机 DP

根据“稳定”的定义，任何合法子序列的末尾，只可能是1个或2个连续相同奇偶性的元素。我们用 4 个变量记录这 4 种状态的数量。

处理每个数时，分情况更新：

· 当前元素单独成序列：产生 1 个新序列。
· 追加到末尾奇偶性不同的序列：末尾变成1个新元素，这部分数量直接累加。
· 追加到末尾奇偶性相同的序列：只能追加上一步末尾连续长度为 1 的序列，使其长度变为 2。

你给出的示例 nums = [1,3,5] 全是奇数，执行过程如下：

· 处理 1：得到 [1]，f[1][0]=1
· 处理 3：得到 [3]、追加得到 [1,3]，f[1][0]=2, f[1][1]=1
· 处理 5：得到 [5]，追加得到 [1,5], [3,5]，长度2状态得到 [1,3,5]? 不会，因为无法从长度2状态追加。最终总数=6。

按顺序更新状态时，需使用旧值计算，C++ 代码中通过临时变量 newLen1、newLen2 避免了覆盖问题。