CF2226G.Stop Spot

You are given an array $a$ of size $n$ ($1 \leq a_i \leq m$).

Consider all $m!$ permutations of the array $[1, 2, \ldots, m]$. For any permutation $p$, define the array $b_p$ as the array formed by concatenating the array $a$ and the permutation $p$. More formally, $b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$.

Let $f(i)$ denote the number of permutations $p$ such that the array $b_p$ contains exactly $i$ palindromic$^{\text{∗}}$ subarrays of even length.

Your task is to compute $$ \sum_{i=0}^{10{100}} f(i)^{i+1}.$$

Since the answer may be large, it should be computed modulo $998\,244\,353$.

$^{\text{∗}}$An array $[c_1, c_2, \ldots, c_k]$ is said to be palindromic if $c_i = c_{k+1-i}$ for all $1 \le i \le k$.

给你一个长度为 $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)$ 表示满足“数组 $b_p$ 中恰好包含 $i$ 个偶长度回文子数组”的排列 $p$ 的个数。

你的任务是计算

$$\sum_{i=0}^{10^{100}} f(i)^{i+1}.$$

由于答案可能很大，需对 $998\,244\,353$ 取模。

$^{\text{∗}}$ 数组 $[c_1, c_2, \ldots, c_k]$ 被称为回文数组，当且仅当对所有 $1 \le i \le k$，均有 $c_i = c_{k+1-i}$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le m \le n \le 10^6$).

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）—— 数组的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each testcase, print a single integer on a new line — $ \sum_{i=0}^{10{100}} f(i)^{i+1}$ modulo $998\,244\,353$.

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

In the first test case, $n=4$, $m=3$, and $a=[3,1,2,1]$.

Let's list all permutations and calculate the number of palindromic subarrays of even length:

• $p_1 = [1, 2, 3]$, $b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$, and the number of palindromic subarrays of even length is $2$.
• $p_2 = [1, 3, 2]$, $b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$, and the number of palindromic subarrays of even length is $1$.
• $p_3 = [2, 1, 3]$, $b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$, and the number of palindromic subarrays of even length is $0$.
• $p_4 = [2, 3, 1]$, $b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$, and the number of palindromic subarrays of even length is $0$.
• $p_5 = [3, 1, 2]$, $b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$, and the number of palindromic subarrays of even length is $0$.
• $p_6 = [3, 2, 1]$, $b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$, and the number of palindromic subarrays of even length is $0$.

Thus, we have $f(0) = 4$, $f(1) = 1$, $f(2) = 1$, and $f(i) = 0$ for all $i \gt 2$. Hence, the answer is $4^1 + 1^2 + 1^3 = 6$.

在第一个测试用例中，$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$，且对所有 $i > 2$ 有 $f(i) = 0$。故答案为 $4^1 + 1^2 + 1^3 = 6$。