CF1349F1 Slime and Sequences (Easy Version)

定义一个长 $n$ 的正整数序列是好的，当且仅当对于每一个出现过的 $k$（$k>1$），其最后一次出现前 $k-1$ 出现过。

给定 $n$，对于每个 $i\in[1,n]$ 求所有好序列中 $i$ 的出现次数和，对 $998244353$ 取模。

$1\le n\le 5000$。

首先显然好序列的值域是从 $1$ 开始的某个前缀。

不知道怎么想到的，存在好序列到 $n$ 的排列的类似反链和最小链覆盖的双射：（题解说是打表发现答案总和是 $n!\times n$）

• 序列 $a$ 到排列 $p$：从 $1$ 开始遍历每个值，将其在 $a$ 中的出现位置从后往前加入排列 $p$ 中；
• 排列 $p$ 到序列 $a$：$a_{p_i}=1+\sum\limits_{j=1}^{i-1}[p_j<p_{j+1}]$；

那么对于每个数 $i$，$a_j=i$ 的方案数就是 $f_{i,j-1}\times \binom{n}{j}\times (n-j)!$，其中 $f_{i,j}$ 为长 $i$ 的有 $j$ 个 $a_{k}<a_{k+1}$ 的位置的排列个数，这个可以 $O(n^2)$ 递推出来（考虑插入 $i+1$ 的影响）。

总时间复杂度 $O(n^2)$。