Almost Perfect

题意翻译

对于排列 $p$，我们称它是基本完美的，当且仅当排列 $p$ 的逆，$q$，满足 $\forall 1\le i\le n,|p_i-q_i|\le 1$。一个排列的逆是满足 $\forall 1\le i\le n,q_{p_i}=i$ 的唯一排列。 输出 $1\sim n$ 的基本完美排列的数量，对 $998244353$ 取模。 本题多测。 数据范围：$T\le 1000$，$1\le n,\sum n\le 3\times 10^5$。

题目描述

A permutation $ p $ of length $ n $ is called almost perfect if for all integer $ 1 \leq i \leq n $ , it holds that $ \lvert p_i - p^{-1}_i \rvert \le 1 $ , where $ p^{-1} $ is the inverse permutation of $ p $ (i.e. $ p^{-1}_{k_1} = k_2 $ if and only if $ p_{k_2} = k_1 $ ). Count the number of almost perfect permutations of length $ n $ modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The description of each test case follows. The first and only line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 3 \cdot 10^5 $ ) — the length of the permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the number of almost perfect permutations of length $ n $ modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3
2
3
50

输出样例 #1

2
4
830690567

说明

For $ n = 2 $ , both permutations $ [1, 2] $ , and $ [2, 1] $ are almost perfect. For $ n = 3 $ , there are only $ 6 $ permutations. Having a look at all of them gives us: - $ [1, 2, 3] $ is an almost perfect permutation. - $ [1, 3, 2] $ is an almost perfect permutation. - $ [2, 1, 3] $ is an almost perfect permutation. - $ [2, 3, 1] $ is NOT an almost perfect permutation ( $ \lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2 $ ). - $ [3, 1, 2] $ is NOT an almost perfect permutation ( $ \lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2 $ ). - $ [3, 2, 1] $ is an almost perfect permutation. So we get $ 4 $ almost perfect permutations.

题目大意：
一个长度为n的排列p被称为基本完美排列，如果对于所有整数1≤i≤n，都满足|p_i - p^{-1}_i| ≤ 1，其中p^{-1}是排列p的逆排列（即p^{-1}_{k1} = k2当且仅当p_{k2} = k1）。

计算长度为n的基本完美排列的数量，对998244353取模。

输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。每个测试用例的描述如下。
每个测试用例的第一行（也是唯一一行）包含一个整数n（1≤n≤3×10^5）——排列的长度。
保证所有测试用例的n之和不超过3×10^5。

输出格式：
对于每个测试用例，输出一个整数——长度为n的基本完美排列的数量，对998244353取模。

输入输出样例：
输入样例 #1
```
3
2
3
50
```
输出样例 #1
```
2
4
830690567
```题目大意： 一个长度为n的排列p被称为基本完美排列，如果对于所有整数1≤i≤n，都满足|p_i - p^{-1}_i| ≤ 1，其中p^{-1}是排列p的逆排列（即p^{-1}_{k1} = k2当且仅当p_{k2} = k1）。 计算长度为n的基本完美排列的数量，对998244353取模。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行（也是唯一一行）包含一个整数n（1≤n≤3×10^5）——排列的长度。 保证所有测试用例的n之和不超过3×10^5。 输出格式： 对于每个测试用例，输出一个整数——长度为n的基本完美排列的数量，对998244353取模。 输入输出样例： 输入样例 #1 ``` 3 2 3 50 ``` 输出样例 #1 ``` 2 4 830690567 ```