CF1726E Almost Perfect

长度为 $n$ 的排列 $p$ 被称为“几乎完美排列”，如果对于所有整数 $1 \leq i \leq n$，都有 $|p_i - p^{-1}_i| \le 1$，其中 $p^{-1}$ 表示 $p$ 的逆排列（即当且仅当 $p_{k_2} = k_1$ 时，$p^{-1}_{k_1} = k_2$）。 请计算长度为 $n$ 的“几乎完美排列”的数量，对 $998244353$ 取模。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示排列的长度。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示长度为 $n$ 的“几乎完美排列”的数量，对 $998244353$ 取模。

对于 $n = 2$，排列 $[1, 2]$ 和 $[2, 1]$ 都是“几乎完美排列”。 对于 $n = 3$，共有 $6$ 个排列。逐一检查如下： - $[1, 2, 3]$ 是“几乎完美排列”。 - $[1, 3, 2]$ 是“几乎完美排列”。 - $[2, 1, 3]$ 是“几乎完美排列”。 - $[2, 3, 1]$ 不是“几乎完美排列”（$|p_2 - p^{-1}_2| = |3 - 1| = 2$）。 - $[3, 1, 2]$ 不是“几乎完美排列”（$|p_2 - p^{-1}_2| = |1 - 3| = 2$）。 - $[3, 2, 1]$ 是“几乎完美排列”。 因此，共有 $4$ 个“几乎完美排列”。 由 ChatGPT 4.1 翻译