题解

思路

按位置从左到右动态规划。

做法

对每个值 $j$，记录当前前缀以 $j$ 结尾的合法方案数，并另外记录每个位置新开始一段连续 $j$ 的方案数。若当前位置允许填 $j$，新开一段的方案数等于上一位置的总方案数减去上一位置已经以 $j$ 结尾的方案数；以 $j$ 结尾的方案只允许保留最近 $j$ 个起点，同时不能跨过最近一个不允许填 $j$ 的位置。用前缀和或滑动窗口即可在 $O(1)$ 时间完成每个 $(位置,j)$ 的转移，所有以不同 $j$ 结尾的方案之和就是当前前缀的答案。

复杂度

共有 $N^2$ 个状态，时间复杂度为 $O(N^2)$，空间复杂度为 $O(N^2)$；所有加减法都对 $998244353$ 取模。