AT_arc114_c [ARC114C] Sequence Scores

对于由 $1$ 到 $M$ 之间的整数构成的长度为 $N$ 的数列 $A$，定义 $f(A)$ 如下： - 存在一个长度为 $N$ 的数列 $X$，初始时所有元素均为 $0$。$f(A)$ 表示通过以下操作将 $X$ 变为 $A$ 所需的最少操作次数。 - 可以指定 $1 \leq l \leq r \leq N$ 和 $1 \leq v \leq M$，将 $l \leq i \leq r$ 的所有 $X_i$ 替换为 $\max(X_i, v)$。 作为 $A$ 的所有可能的数列共有 $M^N$ 种。请计算所有这些数列对应的 $f(A)$ 之和，并对 $998244353$ 取模。

输入从标准输入读取，格式如下： > $N$ $M$

输出所有数列对应的 $f(A)$ 之和对 $998244353$ 取模的结果。

## 限制条件 - $1 \leq N, M \leq 5000$ - 输入均为整数 ## 样例解释 1 共有 $3^2 = 9$ 种数列，对应的 $f$ 值如下： - 当 $A = (1, 1)$ 时，只需一次操作 $(l=1, r=2, v=1)$，所以 $f(A) = 1$。 - 当 $A = (1, 2)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=2, r=2, v=2)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (1, 3)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=2, r=2, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (2, 1)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=1, r=1, v=2)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (2, 2)$ 时，只需一次操作 $(l=1, r=2, v=2)$，所以 $f(A) = 1$。 - 当 $A = (2, 3)$ 时，先操作 $(l=1, r=2, v=2)$，再操作 $(l=2, r=2, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (3, 1)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=1, r=1, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (3, 2)$ 时，先操作 $(l=1, r=2, v=2)$，再操作 $(l=1, r=1, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。 - 当 $A = (3, 3)$ 时，只需一次操作 $(l=1, r=2, v=3)$，所以 $f(A) = 1$。 这些 $f(A)$ 的和为 $3 \times 1 + 6 \times 2 = 15$。 由 ChatGPT 4.1 翻译