1955. 统计特殊子序列的数目

发表于 分类于 阅读次数： Waline： 本文字数： 696 阅读时长 ≈ 2 分钟

考点

  • 状态机DP

思路

状态设计与转移方程说明

问题结构概述

给定一个仅由数字 \(0,1,2\) 构成的数组，需要统计满足以下形式的非空子序列数量： \[ \underbrace{0\cdots 0}_{\ge 1} \underbrace{1\cdots 1}_{\ge 1} \underbrace{2\cdots 2}_{\ge 1} \] 即子序列必须严格按 0 段 → 1 段 → 2 段 的顺序构成，每一段至少包含一个元素。

该问题的核心在于：每个合法子序列在构造过程中，只会处于三种阶段之一，因此可以用常数个状态完成动态规划。

状态定义

在扫描数组前 \(i\) 个元素后，定义以下三个状态变量：

  • \(a_i\)：仅由若干个 \(0\) 组成的非空子序列个数
  • \(b_i\)：形如 \(0\cdots0\,1\cdots1\) 的非空子序列个数
  • \(c_i\)：形如 \(0\cdots0\,1\cdots1\,2\cdots2\) 的非空子序列个数

其中，\(c_i\) 即为最终所求答案。

初始状态为： \[ a_0 = b_0 = c_0 = 0 \]

状态转移思想

对数组进行一次线性扫描。设当前读入的元素为 \(x\)，每个已有子序列对 \(x\) 都只有两种选择：

  1. 不选当前元素：子序列保持不变
  2. 选当前元素：若满足阶段约束，则扩展该子序列

这正是状态“倍增 + 引入”的来源。

状态转移方程

情况一：当前元素为 \(0\)

  • 已有的每一个 \(0\)-子序列，都可以选择“选或不选”当前的 \(0\)，贡献为 \(2a\)
  • 还可以从空序列新生成一个只包含当前 \(0\) 的子序列，贡献为 \(+1\)

因此： \[ a \leftarrow 2a + 1 \] 此时不可能生成包含 \(1\) 或 \(2\) 的合法序列： \[ b, c \text{ 保持不变} \]

情况二：当前元素为 \(1\)

  • 每一个已有的 \(01\)-子序列可以选择是否追加该 \(1\)，贡献为 \(2b\)
  • 任意一个纯 \(0\)-子序列都可以接上该 \(1\)，形成新的 \(01\)-子序列，贡献为 \(+a\)

因此： \[ b \leftarrow 2b + a \] 状态 \(a, c\) 不发生变化。

情况三：当前元素为 \(2\)

  • 每一个已有的 \(012\)-子序列可以选择是否追加该 \(2\)，贡献为 \(2c\)
  • 任意一个 \(01\)-子序列都可以接上该 \(2\)，形成新的合法序列，贡献为 \(+b\)

因此： \[ c \leftarrow 2c + b \] 状态 \(a, b\) 不发生变化。

完整转移汇总

在模 \(M = 10^9 + 7\) 意义下，状态转移可统一写为： \[ \begin{cases} a = 2a + 1, & \text{if } x = 0 \\ b = 2b + a, & \text{if } x = 1 \\ c = 2c + b, & \text{if } x = 2 \end{cases} \quad (\bmod\ M) \]

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5, mod = 1e9 + 7;
    int countSpecialSubsequences(vector<int>& nums) {
        long long a = 0, b = 0, c = 0;
        for (int& x : nums) {
            if (x == 0)
                a = (2 * a + 1) % mod;
            else if (x == 1)
                b = (2 * b + a) % mod;
            else
                c = (2 * c + b) % mod;
        }
        return c;
    }
};