AT_arc163_f.[ARC163F] Many Increasing Problems

PCT 君 出了如下题目。

递增问题
给定一个长度为 $N$ 的非负整数序列 $A_1,A_2,\dots,A_N$。你可以进行任意次数（也可以不进行）的如下操作：

• 选择一个满足 $1 \le i \le N$ 的整数 $i$，将 $A_i$ 增加 $1$ 或减少 $1$。

你的目标是将 $A$ 变为广义单调递增序列。请你求出达成目标所需的最小操作次数。

PCT 君认为这个问题太简单，不适合放在比赛最后，于是将其改编如下：

多个递增问题
长度为 $N$ 且所有元素都在 $1$ 到 $M$ 之间的整数序列 $A$ 一共有 $M^N$ 个。对于所有这样的序列 $A$，将其对应的 递增问题 的答案求和，并对 $998244353$ 取模，输出结果。

请你解决 多个递增问题。

输入为一行，格式如下：

$N$ $M$

输出 多个递增问题 的答案。

数据范围

• $1 \le N, M \le 10^5$

样例解释 1

长度为 $2$，所有元素在 $1$ 到 $2$ 之间的数列共有 $M^N = 4$ 个。对于每个序列 $A$，其 递增问题 的答案如下：

• $A=(1,1)$ 时，答案为 $0$
• $A=(1,2)$ 时，答案为 $0$
• $A=(2,1)$ 时，答案为 $1$
• $A=(2,2)$ 时，答案为 $0$

因此，答案为 $0+0+1+0=1$。

由 ChatGPT 4.1 翻译