本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-25 22:27:32

:::::info[题目基本信息] 考察：动态规划 DP（个人认为是紫，也可能是我太菜了）。
题目简介：
给定 $\{op_n\}$，值域为 $\{0,1,2,3\}$，问有多少 $n$ 阶排列满足（对 $998244353$ 取模）：

• $\displaystyle\forall i\in(1,n],op_i=0\Rightarrow a_i<\min_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in(1,n],op_i=1\Rightarrow a_i>\max_{j=1}^{i-1}a_j$
• $\displaystyle\forall i\in[1,n),op_i=2\Rightarrow a_i<\min_{j=i+1}^na_j$
• $\displaystyle\forall i\in[1,n),op_i=3\Rightarrow a_i>\max_{j=i+1}^na_j$

数据范围：

• $1\le n\le 5000$
• $\forall i\in[1,n],op_i\in\{0,1,2,3\}$ ::::: 对于排列，套路地上连续段 DP，套路地设 $f_{i,j}$ 表示考虑到 $a_{pos}\in[1,i]$ 的所有 $pos$，它们形成了 $j$ 个连续段，至于状态细节不必管，反正最后我尝试的状态都寄了。
  那咋办？！？！？！
  :::::info{open} 不只尝试改变连续段的定义，还要尝试改变连续段定义于的对象。谁告诉你连续段 DP 只能对值域 DP 的？
  切记 DP 题不是套板子题。
  如果你看不懂下面的内容就在心里默念：连续段 DP 是在相对位置上进行 DP，并手玩验证每一种方案都能构造出实例。 ::::: 尝试改变状态的定义，设 $f_{i,j}$ 为考虑到 $[1,i]$ 的所有 $pos$，未被考虑的位置可以在 $j$ 个值域连续段（中间没有已填位置的段）填，先判掉无解情况（存在一个 $2$ 位于 $0$ 左边或者存在一个 $3$ 位于 $1$ 左边），接下来分类讨论：
• $op_i\in\{0,1\}$：
  这时该元素不会对后面的元素造成影响，还会凭空增加一个连续段，所以 DP 数组会整体平移。
• $op_i\in\{2,3\}$：
  这时手玩发现这个位置左右至少有一边位置不能填了，这样会使连续段数量变少（可以不变），所以 DP 数组会整体求后缀和。

按上述简单实现可以通过。
时间复杂度为 $\Theta(n^2)$，空间复杂度为 $\Theta(n)$。

code