题解

思路

共有 $M^N$ 个候选序列。

做法

把 $A$ 映射为 $A'=(A_{P_1},\ldots,A_{P_N})$，这是一个双射，因此在所有满足 $A\ne A'$ 的序列中，$A<A'$ 与 $A>A'$ 的数量相同。只需扣除满足 $A=A'$ 的序列，再除以二。

条件 $A=A'$ 等价于对每个 $i$ 都有 $A_i=A_{P_i}$。把排列分解成 $C$ 个环后，同一环上的所有位置必须取相同值，而不同环可以独立选择，所以共有 $M^C$ 个不动序列。答案即 $\frac{M^N-M^C}{2}\bmod 998244353$。

复杂度

线性遍历排列即可求出环数，两次快速幂的复杂度为 $O(\log N)$，总时间复杂度 $O(N+\log N)$，空间复杂度 $O(N)$。