CF2226G Stop Spot

给定一个长度为 $n$ 的数组 $a$（$1 \leq a_i \leq m$）。 考虑数组 $[1, 2, \ldots, m]$ 的所有 $m!$ 种排列。对于每个排列 $p$，定义数组 $b_p$ 为将数组 $a$ 和排列 $p$ 首尾相连得到的新数组。即，$b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$。 令 $f(i)$ 表示有多少个排列 $p$，使得数组 $b_p$ 恰好包含 $i$ 个偶数长度回文子数组。 你的任务是计算 $$ \sum_{i=0}^{10^{100}} f(i)^{i+1} $$ 的值。 由于答案可能很大，输出对 $998\,244\,353$ 取模后的结果。 注：如果一个数组 $[c_1, c_2, \ldots, c_k]$ 满足 $c_i = c_{k+1-i}$ 对所有 $1 \le i \le k$ 成立，那么它是回文数组。

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^5$）。 接下来每个测试用例，第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$），表示数组 $a$ 的元素。 保证所有测试用例的 $n$ 之和不超过 $10^6$。

每个测试用例输出一行一个整数，表示 $\sum_{i=0}^{10^{100}} f(i)^{i+1}$ 对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，$n=4$，$m=3$，$a=[3,1,2,1]$。 我们列出所有排列并计算偶数长度回文子数组的数量： - $p_1 = [1, 2, 3]$，$b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$，偶数长度回文子数组的个数为 $2$。 - $p_2 = [1, 3, 2]$，$b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$，偶数长度回文子数组的个数为 $1$。 - $p_3 = [2, 1, 3]$，$b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$，偶数长度回文子数组的个数为 $0$。 - $p_4 = [2, 3, 1]$，$b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$，偶数长度回文子数组的个数为 $0$。 - $p_5 = [3, 1, 2]$，$b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$，偶数长度回文子数组的个数为 $0$。 - $p_6 = [3, 2, 1]$，$b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$，偶数长度回文子数组的个数为 $0$。 因此，$f(0)=4$，$f(1)=1$，$f(2)=1$，其余 $f(i)=0$。所以答案为 $4^1+1^2+1^3=6$。 由 ChatGPT 5 翻译