[Solution] Almost Perfect solution codeforces

Almost Perfect solution codeforces – A permutation 𝑝p of length 𝑛n is called almost perfect if for all integer 1𝑖𝑛1≤i≤n, it holds that |𝑝𝑖𝑝1𝑖|1|pi−pi−1|≤1, where 𝑝1p−1 is the inverse permutation of 𝑝p (i.e. 𝑝1𝑘1=𝑘2pk1−1=k2 if and only if 𝑝𝑘2=𝑘1pk2=k1).

Table of Contents

[Solution] Almost Perfect solution codeforces

Count the number of almost perfect permutations of length 𝑛n modulo 998244353998244353.

Input

The first line contains a single integer 𝑡t (1𝑡10001≤t≤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𝑛31051≤n≤3⋅105) — the length of the permutation.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 31053⋅105.

Output

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

[Solution] Almost Perfect solution codeforces

input

Copy
3
2
3
50
output

Copy
2
4
830690567

[Solution] Almost Perfect solution codeforces

For 𝑛=2n=2, both permutations [1,2][1,2], and [2,1][2,1] are almost perfect.

For 𝑛=3n=3, there are only 66 permutations. Having a look at all of them gives us:

  • [1,2,3][1,2,3] is an almost perfect permutation.
  • [1,3,2][1,3,2] is an almost perfect permutation.
  • [2,1,3][2,1,3] is an almost perfect permutation.
  • [2,3,1][2,3,1] is NOT an almost perfect permutation (|𝑝2𝑝12|=|31|=2|p2−p2−1|=|3−1|=2).
  • [3,1,2][3,1,2] is NOT an almost perfect permutation (|𝑝2𝑝12|=|13|=2|p2−p2−1|=|1−3|=2).
  • [3,2,1][3,2,1] is an almost perfect permutation.

So we get 44 almost perfect permutations.

 

3

For Solution

“Click Here”

Leave a Comment