C. Beautiful Sequence 解题思路

摘要与问题转化

本题要求在一个仅包含数字 $ 1, 2, 3$ 的序列中，计算“完美子序列”的数量。一个完美子序列定义为形如 $ 1, 2, \dots, 2, 3$ 的序列，即以 $ 1$ 开头、以 $ 3$ 结尾，中间可以包含零个或多个 $ 2$。 由于序列的结构非常明确，我们不需要关注 $2$ 的具体数量，只需要统计以 $1$ 结尾的子序列数量、以 $2$ 结尾的子序列数量以及以 $3$ 结尾的（即完美）子序列数量。当遍历到当前的数字 $x$ 时，它可以通过衔接一个以 $x-1$ 结尾的子序列，从而形成新的以 $x$ 结尾的子序列。同时，如果 $x=2$，它可以衔接**任何一个**已存在的以 $2$ 结尾的子序列，从而生成新的以 $2$ 结尾的子序列。

主体分析：动态规划策略

1. 状态定义

我们采用动态规划（Dynamic Programming, DP）来解决这个问题，其时间复杂度为 $O(N)$，可以满足 $N \le 2 \cdot 10^5$ 的数据规模要求。 定义 $dp[i]$ 为：以数字 $i$ 结尾的合法子序列的数量。其中 $i \in \{1, 2, 3\}$。
  • $dp[0]$：辅助状态，初始化为 $1$。它表示一个“空子序列”或“起始点”。当遇到 $1$ 时，新的以 $1$ 结尾的子序列数量可以从这个起始点计数 $1$ 开始。

2. 状态转移方程

我们遍历输入的序列，对于当前的数字 $x$：

A. 特殊情况：数字 $x=2$ 的自我转移

数字 $2$ 具有特殊的性质，它可以接在任何一个已存在的以 $2$ 结尾的子序列后面，形成一个新的以 $2$ 结尾的子序列。 如果当前读入的数字 $x=2$，则： $$ dp[2] \leftarrow dp[2] + dp[2] $$ 这个操作表示：对于已有的 $dp[2]$ 个以 $2$ 结尾的子序列，新的 $2$ 都可以接在它们后面，使得数量翻倍。由于 $2$ 的自我衔接不依赖于 $1$ 的转移，因此应先进行。

B. 核心递推：从 $x-1$ 转移到 $x$

数字 $x$ 可以接在所有以 $x-1$ 结尾的子序列后面，形成新的以 $x$ 结尾的子序列。 $$ dp[x] \leftarrow dp[x] + dp[x-1] $$
  • **当 $x=1$ 时：** $dp[1] \leftarrow dp[1] + dp[0]$。所有以 $1$ 结尾的子序列数量增加了 $dp[0]=1$（新的 $1$ 本身作为子序列）个。
  • **当 $x=2$ 时：** $dp[2] \leftarrow dp[2] + dp[1]$。以 $2$ 结尾的子序列数量增加了所有以 $1$ 结尾的子序列的数量。
  • **当 $x=3$ 时：** $dp[3] \leftarrow dp[3] + dp[2]$。以 $3$ 结尾的完美子序列数量增加了所有以 $2$ 结尾的子序列的数量。

3. 实现细节与模运算

由于结果可能非常大，我们需要在每一步加法操作时对结果取模 $MOD = 998244353$。

C++ 代码实现

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

// 定义模数
constexpr int MOD = 998244353;

// 安全的模加法函数
int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}

void solve() {

    int n;
    cin >> n;

    // dp[0]: 初始状态 (1)
    // dp[1]: 以 1 结尾的子序列数量
    // dp[2]: 以 2 结尾的子序列数量
    // dp[3]: 以 3 结尾的完美子序列数量 (最终结果)
    vector<int> dp(4, 0);
    dp[0] = 1; // 初始化起始计数

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // 步骤 A: 特殊转移 (仅当 x=2 时，实现 dp[2] = dp[2] * 2)
        if (x == 2) {
            dp[x] = add(dp[x], dp[x]);
        }

        // 步骤 B: 核心递推 (dp[x] += dp[x-1])
        // x=1 时: dp[1] += dp[0]
        // x=2 时: dp[2] += dp[1]
        // x=3 时: dp[3] += dp[2]
        dp[x] = add(dp[x], dp[x - 1]);
    }

    // dp[3] 即为完美子序列的总数
    cout << dp[3] << '\n';

}


int main() {

    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}