3351. 好子序列的元素之和

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

考点

  • 线性DP

思路

一、问题描述

给定一个整数数组 nums，定义一个好子序列为满足以下条件的子序列：

  • 子序列中任意相邻两个元素的绝对差值为 1。

要求计算 所有好子序列的元素和之和，结果对 \[ \text{MOD} = 10^9 + 7 \] 取模。

二、问题建模思路

1. 按“结尾值”建模而非按位置

注意到题目对顺序敏感，但合法性仅与相邻元素的值有关。 因此可以不关心子序列的具体位置结构，而是按“子序列最后一个元素的值”进行分类统计。

2. 核心观察

若一个好子序列以值 \(v\) 结尾，那么在其末尾追加一个新元素 \(x\) 后仍为好子序列，当且仅当： \[ |x - v| = 1 \quad \Longleftrightarrow \quad v \in \{x-1, x+1\} \] 此外，单个元素 \([x]\) 本身也是一个好子序列。

三、状态定义

设当前已经扫描到数组前缀，定义以下两个状态数组：

  • \(\text{cnt}[v]\)：以值 \(v\) 结尾的好子序列个数
  • \(\text{sum}[v]\)：以值 \(v\) 结尾的好子序列中，所有序列的元素和之和

最终答案为所有新生成好子序列的贡献之和。

四、状态转移推导

1. 新元素 \(x\) 带来的新子序列来源

当处理到一个新元素 \(x\) 时，新生成的、以 \(x\) 结尾的好子序列来自三部分：

  1. 新建单元素子序列 \[ [x] \]

  2. 从所有以 \(x-1\) 结尾的好子序列扩展

  3. 从所有以 \(x+1\) 结尾的好子序列扩展

2. 新增子序列数量

设： \[ \begin{aligned} c_{x-1} &= \text{cnt}[x-1] \\ c_{x+1} &= \text{cnt}[x+1] \end{aligned} \] 则本轮新增的好子序列个数为： \[ \Delta \text{cnt} = 1 + c_{x-1} + c_{x+1} \]

3. 新增子序列的元素和贡献

设： \[ \begin{aligned} s_{x-1} &= \text{sum}[x-1] \\ s_{x+1} &= \text{sum}[x+1] \end{aligned} \]

  • 原有子序列的和整体继承： \[ s_{x-1} + s_{x+1} \]

  • 每个新子序列末尾新增一个 \(x\)，贡献： \[ x \times \Delta \text{cnt} \]

因此新增的元素和为： \[ \Delta \text{sum} = s_{x-1} + s_{x+1} + x \cdot (1 + c_{x-1} + c_{x+1}) \]

4. 状态更新方程

\[ \begin{aligned} \text{cnt}[x] &\leftarrow \text{cnt}[x] + \Delta \text{cnt} \\ \text{sum}[x] &\leftarrow \text{sum}[x] + \Delta \text{sum} \end{aligned} \]

同时，将本轮新增贡献累加到全局答案中： \[ \text{ans} \leftarrow \text{ans} + \Delta \text{sum} \] 所有运算均对 \(\text{MOD}\) 取模。

五、算法流程

  1. 初始化数组 cnt[]、sum[] 为 0
  2. 从左到右扫描 nums
  3. 对当前元素 \(x\)，读取 x-1、x+1 的状态
  4. 按转移方程计算新增贡献
  5. 更新状态并累加答案
  6. 返回最终答案

六、复杂度分析

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

  • 空间复杂度： \[ O(V) \] 其中 \(V\) 为值域上界（本题中 \(\le 10^5\)）

七、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
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const int mod  = 1e9 + 7;
    static const int inf  = 1e5;

    int sumOfGoodSubsequences(vector<int>& nums) {
        // cnt[v]：以值 v 结尾的好子序列个数
        // f[v]  ：以值 v 结尾的好子序列的元素和之和
        long long cnt[maxn] = {};
        long long f[maxn]   = {};

        long long res = 0;  // 全局答案

        for (int x : nums) {
            int pre = x - 1;
            int nxt = x + 1;

            long long c = 0; // 本轮新增的子序列个数（不含 +1 前）
            long long s = 0; // 本轮继承的旧子序列元素和

            // 从 x-1 结尾的子序列扩展
            if (pre >= 0) {
                c = (c + cnt[pre]) % mod;
                s = (s + f[pre])   % mod;
            }

            // 从 x+1 结尾的子序列扩展
            if (nxt <= inf) {
                c = (c + cnt[nxt]) % mod;
                s = (s + f[nxt])   % mod;
            }

            // 加上新建的单元素子序列 [x]
            c = (c + 1) % mod;

            // 新增子序列的元素和：
            // 继承的旧和 + 每个新子序列末尾新增的 x
            s = (s + c * x % mod) % mod;

            // 更新以 x 结尾的状态
            cnt[x] = (cnt[x] + c) % mod;
            f[x]   = (f[x]   + s) % mod;

            // 累加本轮新增贡献
            res = (res + s) % mod;
        }

        return (int)res;
    }
};