题解

思路

对一个已经确定的序列 $A$，其连通块一定对应若干连续区间，而且位置 $i$ 与 $i+1$ 分属不同连通块，当且仅当 $\min(A_1,\ldots,A_i)>\max(A_{i+1},\ldots,A_N)$。

做法

因此可以交换求和顺序：答案等于全部补全方案数，再加上每个分界 $i$ 满足上述严格不等式的补全方案数。固定一个分界，枚举左半部分的最小值 $v$；左侧固定元素必须不小于 $v$，右侧固定元素必须小于 $v$。若左侧有 $l$ 个未知数，其最小值恰为 $v$ 的方案数由 $(M-v+1)^l-(M-v)^l$ 得到；当某个左侧固定元素本身等于 $v$ 时则直接为 $(M-v+1)^l$。若右侧有 $r$ 个未知数，它们都小于 $v$ 的方案数为 $(v-1)^r$。

预处理每个底数 $0,1,\ldots,M$ 的 $0$ 到 $N$ 次幂，并用前缀、后缀数组记录未知数个数、左侧固定最小值和右侧固定最大值，就能在 $O(1)$ 时间取得一次枚举所需的全部信息。

复杂度

共有 $N-1$ 个分界，每个分界枚举 $M$ 个最小值，故时间复杂度为 $O(NM)$，空间复杂度为 $O(NM)$。