好的序列

形式化题目

给定正整数序列 $a_1..a_n$ ，统计整数序列 $b_1..b_n$ 的数量，满足：

$1 \leqslant b_i \leqslant a_i$ （每个位置的上界逐位不同）；
任意相邻两项 $b_i \neq b_{i+1}$ 。

答案对 $998244353$ 取模。其中 $n \leqslant 10^6$ ， $a_i \leqslant 10^9$ 。

样例：a = [2,2,2] 时只有 $\{1,2,1\},\{2,1,2\}$ ，答案是 $2$ 。

思路

一句话本质：“相邻都不相等"是一个全局耦合约束，正着数很难；反过来把"哪些位置相邻相等”（坏点）当成可指定的集合——一旦指定，序列就碎成若干"段内同值、段间不限"的独立段，每段的取值方案数恰好是该段 $a$ 的最小值。用容斥把这些计数拼回"零坏点"，段数只以奇偶形式出现在容斥系数里，于是把段数奇偶当状态做 DP，最后用单调栈维护"后缀最小值阶梯"+ 前缀和，把每次转移压成 $O(1)$ ，整体 $O(n)$ 。

先看一个能直接验证想法的朴素解——逐位枚举填数：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:50
 * update_at: 2026-08-28 23:50
 */
// brute.cpp：小数据暴力解，逐位枚举填数：每层递归给 b[dep] 选一个值 v ∈ [1, a[dep]]。
// 生成完整的 b[1..n] 后，在叶子节点检查"任意相邻两项不等"这个合法条件再计数。
// 只适合小数据（n <= 8，a_i <= 5），用于帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;

int n;
int a[MAXN];   // 输入序列
int b[MAXN];   // 当前填出的完整序列
ll ans;        // 好序列个数

// 检查完整 b[1..n] 是否是好序列：任意相邻两项不等
bool check() {
    for (int i = 1; i < n; i++) {
        if (b[i] == b[i + 1]) return false;
    }
    return true;
}

// 第 dep 层在给 b[dep] 选择一个值，选完后递归下一层
void dfs(int dep) {
    if (dep == n + 1) { // 一条完整序列已经生成
        if (check()) ans++;
        return;
    }
    for (int v = 1; v <= a[dep]; v++) {
        b[dep] = v;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    ans = 0;
    dfs(1);

    cout << ans << '\n';
    return 0;
}

这个暴力第 dep 层给 b[dep] 从 $[1, a_{dep}]$ 里选一个值，叶子节点检查完整序列是否相邻不等。它枚举的是"完整序列"，总数量级 $\prod a_i$ ，只能处理 $n \leqslant 8, a_i \leqslant 5$ 的小数据。

问题？直接按值做 DP（ $f[i][j]$ = 以 $b_i = j$ 结尾）为什么也不行？

$j$ 的值域由 $a_i$ 决定，而 $a_i$ 最大 $10^9$ ，值域根本枚举不完。所以必须换一种不看具体值、只看"值域分界点"（即 $a$ 的最小值）的思路。

问题？正着数"所有相邻都不等"到底难在哪？

每个 $b_i$ 同时受 $b_{i-1}$ 和 $b_{i+1}$ 两个邻居约束，按"左边不等、右边不等"正向分类会互相重叠，没法拆成独立子问题。

问题？反过来想：如果强制某些位置相邻相等，序列会变成什么？

把 $b_i = b_{i+1}$ 的位置叫坏点。指定一个坏点集合 $S$ （ $b_i = b_{i+1}$ 强制成立）后，序列被切成若干连续段：段内所有值相等，段与段之间取值互不限制。坏点个数 = $n - $ 段数。全局耦合约束就这样被拆成了互相独立的段。

问题？一段的取值方案数是多少？

段 $[l, r]$ 内所有 $b$ 取同一个值 $v$ ，要求 $v \leqslant a_x$ （ $l \leqslant x \leqslant r$ ），即 $v \in [1, \min(a_l..a_r)]$ ，所以一段的取值方案数 = 该段 $a$ 的最小值。这是整个计数能落地的关键：段内部的选择被压缩成一个"最小值"。

问题？怎么把"指定坏点集合"的计数拼回"零坏点"的答案？

标准容斥：设事件 $A_i$ = “ $b_i = b_{i+1}$ ”，

Ans = \sum_{S \subseteq \{1..n-1\}} (-1)^{|S|} \cdot N(S)

其中 $N(S)$ = 强制 $S$ 中坏点出现的方案数。因为任意一个真实坏点集合为 $T$ 的序列 $b$ 被 $N(S)$ 计数当且仅当 $S \subseteq T$ ，它对右侧的贡献是 $\sum_{S \subseteq T} (-1)^{|S|} = (1-1)^{|T|}$ ，只有 $T = \varnothing$ （好序列）时是 $1$ ，其余全是 $0$ 。

按坏点数分组：设 $f_{n,j}$ = 把前 $n$ 项分成 $j$ 段（段内同值、段间不限）的方案总数，它恰好是所有 $|S| = n - j$ 的 $N(S)$ 之和（段数 $j \iff$ 坏点数 $n - j$ ），于是

Ans = \sum_{j=1}^{n} (-1)^{n-j} \, f_{n,j}

问题？ $f_{i,j}$ 怎么递推？

枚举最后一段的起点 $k$ ：前 $k-1$ 项分成 $j-1$ 段，最后一段 $[k, i]$ 取值为 $\min(a_k..a_i)$ ，乘法原理：

f_{i,j} = \sum_{k=1}^{i} f_{k-1,j-1} \cdot \min(a_k..a_i)

下面用样例 $1$ （ $a = [2,2,2]$ ）的 $f_{i,j}$ 表验证。这张表展示 $j$ 段分段 DP 的完整状态：行是"已处理到第 $i$ 项"，列是"分成 $j$ 段"，单元格是 $f_{i,j}$ ：

$i \backslash j$	1	2	3
1	2	0	0
2	2	4	0
3	2	8	8

观察 $f_{3,2} = 8$ 这一格（至少一轮转移来源）：它由三段拼成—— $f_{3,2} = f_{0,1}\min(a_1..a_3) + f_{1,1}\min(a_2..a_3) + f_{2,1}\min(a_3) = 0\cdot 2 + 2\cdot 2 + 2\cdot 2 = 8$ 。最后答案 $= f_{3,1} - f_{3,2} + f_{3,3} = 2 - 8 + 8 = 2$ ，正是样例输出。

问题？容斥系数 $(-1)^{n-j}$ 里 $j$ 的具体值重要吗？

$n$ 是常数，所以只差 $j$ 的奇偶。按段数奇偶合并两维：

f[i][p] = \sum_{j \equiv p \pmod 2} f_{i,j} \quad (p = 0,1)

多分一段就翻转一次奇偶，转移变成：

f[i][p] = \sum_{k=1}^{i} f[k-1][1-p] \cdot \min(a_k..a_i)

答案 $Ans = (-1)^n \big(f[n][0] - f[n][1]\big)$ ： $n$ 为奇输出 $f[n][1]-f[n][0]$ ，为偶输出 $f[n][0]-f[n][1]$ 。这就是 $O(n^2)$ 的 60pts 做法。

问题？ $O(n^2)$ 的瓶颈在哪？

对每个 $i$ 都要枚举所有 $k$ ，并且每次重新求 $\min(a_k..a_i)$ 。这两个都是 $O(n)$ ，必须同时优化。

问题？固定 $i$ 时， $\min(a_k..a_i)$ 随 $k$ 怎么变化？

$k$ 从 $i$ 往左走，区间变大，最小值只会单调不升，且只在"遇到新的更小值"的位置改变——它是一个阶梯函数，拐点恰好构成一个 $a$ 值严格递增的单调栈。以 $a = [2,1,3]$ 、 $i = 3$ 为例，这张文本图展示后缀最小值阶梯与单调栈的对应关系：

text

1
2
3
4
5
6
7
8
9
10
11固定 i = 3，a = [2, 1, 3]，m(k) = min(a[k..3]) 的阶梯：

m(k)
3 ┤              ┌───┐
  │              │ 3 │   ← k = 3 这一段：min = a[3] = 3
1 ┤──────────────└───┘
  │      min = 1：k = 1..2 这一段（最小值是 a[2] = 1）
  └──────────────────→ k
     1     2     3

拐点位置: 2, 3  ⟺  单调栈 stk = [2, 3]（栈内 a 值严格递增）

图中每段水平线上的 $\min$ 值就是栈内对应拐点的 $a$ 。栈顶被弹出，意味着它被右边更小的值"接管"；压入 $i$ 则产生新的一段。

问题？有了阶梯结构，怎么把 $\sum_k f[k-1][1-p]\cdot m(k)$ 增量维护成 $O(1)$ ？

处理到 $i$ 时先弹出所有 $a \geqslant a_i$ 的栈顶，设 cur = 弹出后的栈顶（栈空为 0）。弹出前那部分阶梯和 $cur$ 时刻完全相同，其加权和就是 $f[cur][p]$ （已经算过）；新产生的只有最后一段 $k \in (cur, i]$ ，其上 $\min = a_i$ ，用前缀和 $g[i][p] = \sum_{t=0}^{i} f[t][p]$ 相减即可：

f[i][p] = f[cur][p] + a_i \cdot \big(g[i-1][1-p] - g[cur-1][1-p]\big)

栈空时 $f[cur][p] = 0$ 。下表用 $a = [2,1,3]$ 走一遍奇偶 DP（ $f$ 与 $g$ 两个状态都列出， $g$ 是 $f$ 的奇偶前缀和），重点看 $i = 3$ 行如何从 $i = 2$ 行增量得到：

$i$	$f[i][0]$	$f[i][1]$	$g[i][0]$	$g[i][1]$	说明
0	1	0	1	0	空前缀分 0 段（偶数）
1	0	2	1	2	栈空， $f[1][1] = a_1\cdot g[0][0] = 2$ ， $g[1][1] = g[0][1] + f[1][1] = 2$
2	2	1	3	3	弹出 $a_1$ ，栈空， $f[2][0] = a_2\cdot g[1][1] = 1\cdot2$ ， $g[2][0] = g[1][0] + f[2][0] = 1+2 = 3$
3	5	7	8	10	栈 $[2,3]$ ； $f[3][0] = f[2][0] + a_3(g[2][1]-g[1][1]) = 2+3\cdot1 = 5$ ； $f[3][1] = 1+3\cdot(3-1) = 7$

验证 $i=3$ ： $f[3][0] = \sum_k f[k-1][1]\,m(k) = f[0][1]\cdot1 + f[1][1]\cdot1 + f[2][1]\cdot3 = 0+2+3 = 5$ ，与增量式一致；答案（ $n$ 奇） $= f[3][1]-f[3][0] = 2$ ，直接枚举 $\{(2,1,2),(2,1,3)\}$ 也是 2。注意 $f[i][0]$ 引用的是奇数前缀和 $g[\cdot][1]$ 、 $f[i][1]$ 引用偶数前缀和——"段数加一翻转奇偶"的体现，这是最容易写错的地方。

实现上：f[MAXN][2]、g[MAXN][2] 存奇偶两维，stk[] 存单调栈（弹出条件 $a[\text{stk}[top]] \geqslant a_i$ ，保证栈内严格递增），cur 就是弹出后的栈顶。所有运算取模，前缀和相减可能为负，乘 $a_i$ 前先取正； $n$ 可达 $10^6$ 需要快读。

代码

cpp

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:50
 * update_at: 2026-08-28 23:50
 */
// main.cpp：T5 好序列(GoodSeq) 最终解。
// 思路：正难则反 + 容斥（坏点 = 相邻相等的位置）-> 分段 DP（段内同值、段间不限）
//       -> 容斥系数只依赖段数奇偶，丢掉 j 维 -> 单调栈 + 前缀和优化 min 枚举，O(n)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 998244353;
const int MAXN = 1000005;

int n;
int a[MAXN]; // 输入序列

// f[i][0/1]：前 i 项分成 偶数段 / 奇数段（段内同值、段间取值不限）的方案总数。
//            即 f[i][p] = Σ_{j ≡ p (mod 2)} f_{i,j}，其中 f_{i,j} 是分成 j 段的总方案。
// g[i][0/1]：f 的按奇偶分别做前缀和，g[i][p] = Σ_{t=0..i} f[t][p]。
int f[MAXN][2], g[MAXN][2];

int stk[MAXN], top; // 单调栈：栈内 a 值严格递增（从栈底到栈顶），
                    // 栈中位置就是"后缀最小值"阶梯函数的所有拐点

// 快速读入一个整数（n 可达 1e6，关闭同步后仍建议快读）
int read_int() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

void read_input() {
    n = read_int();
    for (int i = 1; i <= n; i++) {
        a[i] = read_int();
    }
}

// 模意义下取正数：x 可能在 (-MOD, 2*MOD) 之间
ll M(ll x) { return (x % MOD + MOD) % MOD; }

void solve() {
    // 空序列分成 0 段：0 是偶数，算 1 种（空划分）
    f[0][0] = 1;
    g[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        // 弹出所有 a >= a[i] 的栈顶：它们不再能作为 (k..i) 的最小值拐点
        while (top && a[stk[top]] >= a[i]) top--;
        int cur = top ? stk[top] : 0; // 弹出后栈顶 cur：最后一个 a < a[i] 的拐点位置
        stk[++top] = i;               // 压入 i 作为新的拐点

        // 关键转移：f[i][p] = Σ_{k=1..i} f[k-1][1-p] * min(a[k..i])
        // 后缀最小值 min(a[k..i]) 是阶梯函数：
        //   k ∈ (stk[s-1], stk[s]] 时，min(a[k..i]) = a[stk[s]]
        // 因此总贡献 = f[cur][p]（沿用 cur 处已算好的前 top 层）
        //            + a[i] * (g[i-1][1-p] - g[cur-1][1-p])（新增的最后一段 (cur+1..i)）
        if (cur == 0) {
            // 栈空：阶梯只有最后一段 (1..i)，min = a[i]
            f[i][0] = M((ll)g[i - 1][1] * a[i]);
            f[i][1] = M((ll)g[i - 1][0] * a[i]);
        } else {
            f[i][0] = M(f[cur][0] + M((ll)M(g[i - 1][1] - g[cur - 1][1]) * a[i]));
            f[i][1] = M(f[cur][1] + M((ll)M(g[i - 1][0] - g[cur - 1][0]) * a[i]));
        }

        // 更新按奇偶分组的前缀和
        g[i][0] = M(g[i - 1][0] + f[i][0]);
        g[i][1] = M(g[i - 1][1] + f[i][1]);
    }

    // 答案 = Σ_j (-1)^{n-j} f_{n,j} = (-1)^n * (f[n][0] - f[n][1])
    ll ans;
    if (n & 1) ans = M(f[n][1] - f[n][0]);
    else ans = M(f[n][0] - f[n][1]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间：每个元素至多入栈/出栈一次，每次转移 $O(1)$ ，总计 $O(n)$ 。实测 $n=10^6$ 约 0.18s。
空间： $a, f, g, stk$ 四个 $O(n)$ 数组，约 24MB。

总结

思维链：正向计数卡在"相邻不等的全局耦合" → 正难则反，指定坏点集合把序列切成独立段（段取值数 = 段内最小值）→ 容斥拼回答案 → 系数只差奇偶，丢掉 $j$ 维 → 瓶颈在枚举 $k$ 求 $\min(a_k..a_i)$ → 阶梯函数 + 单调栈 + 前缀和增量维护。
两个易错点：①奇偶交叉引用（ $f[i][0]$ 用 $g[\cdot][1]$ ）；②容斥系数符号：答案 $= (-1)^n(f[n][0]-f[n][1])$ ，奇数 $n$ 要反过来减。
可迁移：任何"强制一段内相同"的计数问题都可以用同样的坏点/段划分 + 容斥框架；"最小值随区间端点变化的阶梯结构用单调栈维护"是 $O(n^2)$ 区间 DP 转 $O(n)$ 的通用手法。

目录

形式化题目

思路

代码

复杂度

总结