AT_nikkei2019_2_final_h 逆にする関数

给定一个由 $1, 2, \dots, m$ 组成的数列 $(v_1, v_2, \dots, v_k)$ 和一个函数 $f\colon \{1, \dots, m\} \to \{1, \dots, m\}$，当 $f$ 满足以下条件时，称 $f$ 能*逆转*数列 $(v_1, v_2, \dots, v_k)$。 - 数列 $(f(v_1), f(v_2), \dots, f(v_k))$ 与原数列反转后的数列 $(v_k, v_{k-1}, \dots, v_1)$ 完全相同。 现给定一个由 $1, 2, \dots, m$ 组成的数列 $(a_1, a_2, \dots, a_n)$。该数列的所有非空连续子序列共有 $\frac{n(n+1)}{2}$ 种。请你统计，对于所有这些连续子序列，能够逆转它们的函数 $f$ 的种数之和，并输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入： > $n$ $m$ $a_1$ $a_2$ $\dots$ $a_n$

输出所有连续子序列对应的逆转函数个数之和，对 $998244353$ 取模后的结果。

### 注意 - 对于函数 $f$ 和 $g$，如果存在 $i \in \{1, \dots, m\}$ 使得 $f(i) \neq g(i)$，则认为 $f$ 和 $g$ 是不同的函数。 ### 约束条件 - $1 \leq n, m \leq 3 \times 10^5$ - 对于每个 $i=1,2,\dots,n$，有 $1 \leq a_i \leq m$ - 输入均为整数 ### 样例解释 1 数列 $(1, 1, 2)$ 的连续子序列有 $(1)$、$(1, 1)$、$(1, 1, 2)$、$(1)$、$(1, 2)$、$(2)$。 - 使 $f$ 能逆转数列 $(1)$ 的充要条件是 $f(1)=1$，此时在 $\{1,2,3\}$ 上的函数共有 $9$ 种。 - 使 $f$ 能逆转数列 $(1, 1)$ 的充要条件是 $f(1)=1$，此时在 $\{1,2,3\}$ 上的函数共有 $9$ 种。 - 使 $f$ 能逆转数列 $(1, 1, 2)$ 的充要条件是 $f(1)=2$ 且 $f(1)=1$ 且 $f(2)=1$，无解。 - 使 $f$ 能逆转数列 $(1, 2)$ 的充要条件是 $f(1)=2$ 且 $f(2)=1$，此时在 $\{1,2,3\}$ 上的函数共有 $3$ 种。 - 使 $f$ 能逆转数列 $(2)$ 的充要条件是 $f(2)=2$，此时在 $\{1,2,3\}$ 上的函数共有 $9$ 种。 因此，答案为 $9 + 9 + 0 + 9 + 3 + 9 = 39$。 ### 样例解释 2 请不要忘记对 $998244353$ 取模。 由 ChatGPT 4.1 翻译